# Some new Decidability Results on Positive and Negative Set Constraints

Abstract : A positive set constraint is of the form exp 1 $\subseteq$ exp 2, a negative set constraint is of the form exp 1 $\subseteq$ exp 2 where exp 1 and exp 2 are set expressions constructed using set variables, function symbols, and the set union, intersection and complement symbols. Decision algorithms for satisfiability of systems of positive and negative set constraints were given by Gilleron et al. [GTT93b], Aiken et al. [AKW93], and Charatonik and Pacholski [CP94]. In this paper, we study properties of the set of solutions of such systems and properties of solutions of interest for applications. The main decidability results are: for positive and negative set constraints, equivalence of systems is decidable, it is decidable whether or not a system has a unique solution; for positive set constraints, it is decidable whether or not a system has a least solution, it is decidable whether or not a system has a finite solution (i.e. the interpretation maps each set variable on a finite set).
Document type :
Conference papers

https://hal.inria.fr/inria-00538880
Contributor : Rémi Gilleron <>
Submitted on : Tuesday, November 23, 2010 - 2:48:38 PM
Last modification on : Tuesday, April 28, 2020 - 11:52:08 AM

### Identifiers

• HAL Id : inria-00538880, version 1

### Citation

Rémi Gilleron, Sophie Tison, Marc Tommasi. Some new Decidability Results on Positive and Negative Set Constraints. Proceedings of First International Conference on Constraints in Computational Logics, CCL'94, 1994, Munich, Germany. pp.336--351. ⟨inria-00538880⟩

Record views