Skip to Main content Skip to Navigation
Journal articles

Automata for Unordered Trees

Adrien Boiret 1 Vincent Hugot 1 Joachim Niehren 1 Ralf Treinen 2
1 LINKS - Linking Dynamic Data
CRIStAL - Centre de Recherche en Informatique, Signal et Automatique de Lille - UMR 9189, Inria Lille - Nord Europe
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.
Document type :
Journal articles
Complete list of metadata

Cited literature [37 references]  Display  Hide  Download
Contributor : Inria Links Connect in order to contact the contributor
Submitted on : Saturday, July 30, 2016 - 1:55:26 PM
Last modification on : Friday, January 21, 2022 - 3:13:18 AM
Long-term archiving on: : Monday, October 31, 2016 - 10:23:44 AM


Files produced by the author(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⟩



Les métriques sont temporairement indisponibles