Constructive negation and constraint logic programming with sets

The aim of this paper is to extend the Constructive Negation technique to t he case of CLP(SET), a Constraint Logic Programming (CLP) language based on hereditarily (and hybrid) finite sets. The challenging aspects of the prob lem originate from the fact that the structure on which CLP(SET) is based i s not admissible closed, and this does not allow to reuse the results prese nted in the literature concerning the relationships between CLP and constru ctive negation. We propose a new constraint satisfaction algorithm, capable of correctly ha ndling constructive negation for large classes of CLP(SET) programs; we als o provide a syntactic characterization of such classes of programs. The res ulting algorithm provides a novel constraint simplification procedure to ha ndle constructive negation, suitable to theories where unification admits m ultiple most general unifiers. We also show, using a general result, that i t 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 negat ion technique is feasible.