Constructive negation and constraint logic programming with sets (TR)

Agostino Dovier, Enrico Pontelli, and Gianfranco Rossi


The aim of this paper is to extend the Constructive Negation technique to the case of CLP(SET), a Constraint Logic Programming 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. We propose a new constraint satisfaction algorithm, capable of dealing with large classes of CLP(SET) programs, and we present a syntactic characterization of such classes. The resulting algorithm provides a novel constraint simplification procedure to handle constructive negation, suitable to those theories where unification admits multiple maximally general unifiers. We also show, using undecidability arguments, that it is impossible to implement a Constructive Negation working on arbitrary CLP(SET) programs with negation---thus proving that classical results regarding Constructive Negation do not scale to the SET domain.

Keywords: Constraint Logic Programming, Constructive Negation, Programming with Sets.

Available: 600 DPI PostScript, BibTeX entry.

[Page last updated on January 29, 2002, 11:16:45.]

Page maintained by
Enea Zaffanella

Home | People | Projects | Publications | Seminars | Software | Links