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.
Document type :
Journal articles
Liste complète des métadonnées

Cited literature [37 references]  Display  Hide  Download

https://hal.inria.fr/hal-01179493
Contributor : Inria Links <>
Submitted on : Saturday, July 30, 2016 - 1:55:26 PM
Last modification on : Friday, March 22, 2019 - 1:35:28 AM
Document(s) archivé(s) le : Monday, October 31, 2016 - 10:23:44 AM

File

DeterministicAutomataUnordered...
Files produced by the author(s)

Identifiers

Citation

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⟩

Share

Metrics

Record views

566

Files downloads

138