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).
Type de document :
Communication dans un congrès
Proceedings of First International Conference on Constraints in Computational Logics, CCL'94, 1994, Munich, Germany. Springer Verlag, 845, pp.336--351, 1994, Lecture Notes in Computer Science
Liste complète des métadonnées

https://hal.inria.fr/inria-00538880
Contributeur : Rémi Gilleron <>
Soumis le : mardi 23 novembre 2010 - 14:48:38
Dernière modification le : mardi 24 avril 2018 - 13:32:52

Identifiants

  • HAL Id : inria-00538880, version 1

Collections

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. Springer Verlag, 845, pp.336--351, 1994, Lecture Notes in Computer Science. 〈inria-00538880〉

Partager

Métriques

Consultations de la notice

214