Solving Systems of Set Constraints with Negated Subset Relationships

Abstract : We present a decision procedure, based on tree automata techniques, for satisfiability of systems of set constraints including negated subset relationships. This result extends all previous works on set constraints solving (Heintze et Jaffar; Aiken et Wimmers; Gilleron, Tison and Tommasi; Bachmair, Gantzinger and Waldmann) and solves a problem which was left open in Bachmair et al. We prove in a constructive way that a non empty set of solutions always contains a regular solution, that is a tuple of regular tree languages. Moreover, we think that the new class of tree automata describes here could be interesting in its own.
Type de document :
Communication dans un congrès
Proceedings of the $34^th$ Symposium on Foundations of Computer Science, FOCS'93, 1993, Palo Alto California, United States. IEEE, pp.372--380, 1993
Liste complète des métadonnées

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

Identifiants

  • HAL Id : inria-00538879, version 1

Collections

Citation

Rémi Gilleron, Sophie Tison, Marc Tommasi. Solving Systems of Set Constraints with Negated Subset Relationships. Proceedings of the $34^th$ Symposium on Foundations of Computer Science, FOCS'93, 1993, Palo Alto California, United States. IEEE, pp.372--380, 1993. 〈inria-00538879〉

Partager

Métriques

Consultations de la notice

164