Automata for Unordered Trees

Adrien Boiret 1 Vincent Hugot 1 Joachim Niehren 1 Ralf Treinen 2
1 LINKS - Linking Dynamic Data
Inria Lille - Nord Europe, CRIStAL - Centre de Recherche en Informatique, Signal et Automatique de Lille (CRIStAL) - UMR 9189
Abstract : We present a framework for defining automata for unordered data trees that is parametrized by the way in which multisets of children nodes are described. Presburger tree automata and alternating Presburger tree automata are particular instances. We establish the usual equivalence in expressiveness of tree automata and MSO for the automata defined in our framework. We then investigate subclasses of automata for unordered trees for which testing language equivalence is in P-time. For this we start from automata in our framework that describe multisets of children by finite automata, and propose two approaches of how to do this deterministically. We show that a restriction to confluent horizontal evaluation leads to polynomial-time emptiness and universality, but still suffers from coNP-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 on the choice of the order, we obtain different classes of automata, each of which has the same expressiveness as Counting MSO.
Type de document :
Article dans une revue
Information and Computation, Elsevier, 2017, 253, pp.304-335 〈10.1016/j.ic.2016.07.012〉
Liste complète des métadonnées

Littérature citée [37 références]  Voir  Masquer  Télécharger
Contributeur : Inria Links <>
Soumis le : samedi 30 juillet 2016 - 13:55:26
Dernière modification le : jeudi 11 janvier 2018 - 06:27:32
Document(s) archivé(s) le : lundi 31 octobre 2016 - 10:23:44


Fichiers produits par l'(les) auteur(s)




Adrien Boiret, Vincent Hugot, Joachim Niehren, Ralf Treinen. Automata for Unordered Trees. Information and Computation, Elsevier, 2017, 253, pp.304-335 〈10.1016/j.ic.2016.07.012〉. 〈hal-01179493〉



Consultations de la notice


Téléchargements de fichiers