Automata for Unordered Trees
Type de document :
Compte-rendu et recension critique d'ouvrage
DOI :
Titre :
Automata for Unordered Trees
Auteur(s) :
Boiret, Adrien [Auteur]
Linking Dynamic Data [LINKS]
Hugot, Vincent [Auteur]
Linking Dynamic Data [LINKS]
Niehren, Joachim [Auteur]
Linking Dynamic Data [LINKS]
Treinen, Ralf [Auteur]
Preuves, Programmes et Systèmes [PPS]
Linking Dynamic Data [LINKS]
Hugot, Vincent [Auteur]
Linking Dynamic Data [LINKS]
Niehren, Joachim [Auteur]
Linking Dynamic Data [LINKS]
Treinen, Ralf [Auteur]
Preuves, Programmes et Systèmes [PPS]
Titre de la revue :
Information and Computation
Pagination :
304-335
Éditeur :
Elsevier
Date de publication :
2017-04-22
ISSN :
0890-5401
Discipline(s) HAL :
Informatique [cs]/Théorie et langage formel [cs.FL]
Résumé en anglais : [en]
We present a framework for defining automata for unordereddata trees that is parametrized by the way in which multisets of children nodes are described. Presburger tree automata and alternatingPresburger tree automata are ...
Lire la suite >We present a framework for defining automata for unordereddata trees that is parametrized by the way in which multisets of children nodes are described. Presburger tree automata and alternatingPresburger tree automata are particular instances. We establish the usual equivalence in expressiveness of tree automata and MSO for the automata defined inour framework.We then investigate subclasses of automata for unordered treesfor which testing language equivalence is in P-time. For this we start from automata in our framework that describe multisets of childrenby finite automata, and propose two approaches of how todo this deterministically. We show that a restriction to confluent horizontal evaluation leads to polynomial-time emptiness and universality, but still suffers fromcoNP-completeness of the emptiness of binary intersections. Finally, efficient algorithms can be obtained by imposing an order of horizontal evaluation globally for all automata in the class. Depending onthe choice of the order, we obtain different classes of automata, eachof which has the same expressiveness as Counting MSO.Lire moins >
Lire la suite >We present a framework for defining automata for unordereddata trees that is parametrized by the way in which multisets of children nodes are described. Presburger tree automata and alternatingPresburger tree automata are particular instances. We establish the usual equivalence in expressiveness of tree automata and MSO for the automata defined inour framework.We then investigate subclasses of automata for unordered treesfor which testing language equivalence is in P-time. For this we start from automata in our framework that describe multisets of childrenby finite automata, and propose two approaches of how todo this deterministically. We show that a restriction to confluent horizontal evaluation leads to polynomial-time emptiness and universality, but still suffers fromcoNP-completeness of the emptiness of binary intersections. Finally, efficient algorithms can be obtained by imposing an order of horizontal evaluation globally for all automata in the class. Depending onthe choice of the order, we obtain different classes of automata, eachof which has the same expressiveness as Counting MSO.Lire moins >
Langue :
Anglais
Vulgarisation :
Non
Projet ANR :
Collections :
Source :
Fichiers
- https://hal.inria.fr/hal-01179493/document
- Accès libre
- Accéder au document
- https://hal.inria.fr/hal-01179493/document
- Accès libre
- Accéder au document
- https://hal.inria.fr/hal-01179493/document
- Accès libre
- Accéder au document
- document
- Accès libre
- Accéder au document
- DeterministicAutomataUnordered_Journal-1.pdf
- Accès libre
- Accéder au document