Constructive negation and constraint logic programming with sets

The aim of this paper is to extend the Constructive Negation technique to the case of CLP(SET), a Constraint Logic Programming (CLP) language based on hereditarily (and hybrid) finite sets. The challenging aspects of the problem originate from the fact that the structure on which CLP(SET) is based is not admissible closed, and this does not allow to reuse the results presented in the literature concerning the relationships between CLP and constructive negation. We propose a new constraint satisfaction algorithm, capable of correctly handling constructive negation for large classes of CLP(SET) programs; we also provide a syntactic characterization of such classes of programs. The resulting algorithm provides a novel constraint simplification procedure to handle constructive negation, suitable to theories where unification admits multiple most general unifiers. We also show, using a general result, that it is impossible to construct an interpreter for CLP(SET) with constructive negation which is guaranteed to work for any arbitrary program; we identify classes of programs for which the implementation of the constructive negation technique is feasible.