Set constraints and automata

Abstract : We define a new class of automata which is an acceptor model for mappings from the set of terms T? over a ranked alphabet ? into a set E of labels. When E is a set of tuples of binary values, an automaton can be viewed as an acceptor model for n-tuples of tree languages. We prove decidability of emptiness and closure properties for this class of automata. As a consequence of these results, we prove decidability of satisfiability of systems of positive and negative set constraints without projection symbols. We prove the decidability of the satisfiability problem for systems of positive and negative set constraints without projection symbols. Moreover we prove that a non-empty set of solutions always contain a regular solution (i.e., a n-tuple of regular tree languages). We also deduce decidability results for properties of sets of solutions of systems of set constraints.
Type de document :
Article dans une revue
Information and Computation, Elsevier, 1999, 149 (1), pp.1--41
Liste complète des métadonnées

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

Identifiants

  • HAL Id : inria-00538886, version 1

Collections

Citation

Rémi Gilleron, Sophie Tison, Marc Tommasi. Set constraints and automata. Information and Computation, Elsevier, 1999, 149 (1), pp.1--41. 〈inria-00538886〉

Partager

Métriques

Consultations de la notice

127