Some new Decidability Results on Positive and Negative Set Constraints - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Communication Dans Un Congrès Année : 1994

Some new Decidability Results on Positive and Negative Set Constraints

Résumé

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).
Fichier non déposé

Dates et versions

inria-00538880 , version 1 (23-11-2010)

Identifiants

  • HAL Id : inria-00538880 , version 1

Citer

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⟩
104 Consultations
0 Téléchargements

Partager

Gmail Facebook X LinkedIn More