Skip to Main content Skip to Navigation
Journal articles

Rigid Tree Automata and Applications

Florent Jacquemard 1 Francis Klay 2 Camille Vacher 3, 4
1 DAHU - Verification in databases
LSV - Laboratoire Spécification et Vérification [Cachan], Inria Saclay - Ile de France
4 MOSTRARE - Modeling Tree Structures, Machine Learning, and Information Extraction
LIFL - Laboratoire d'Informatique Fondamentale de Lille, Inria Lille - Nord Europe
Abstract : We introduce the class of Rigid Tree Automata (RTA), an extension of standard bottom-up automata on ranked trees with distinguished states called rigid. Rigid states define a restriction on the computation of RTA on trees: RTA can test for equality in subtrees reaching the same rigid state. RTA are able to perform local and global tests of equality between subtrees, non-linear tree pattern matching, and some inequality and disequality tests as well. Properties like determinism, pumping lemma, Boolean closure, and several decision problems are studied in detail. In particular, the emptiness problem is shown decidable in linear time for RTA whereas membership of a given tree to the language of a given RTA is NP-complete. Our main result is the decidability of whether a given tree belongs to the rewrite closure of an RTA language under a restricted family of term rewriting systems, whereas this closure is not an RTA language. This result, one of the first on rewrite closure of languages of tree automata with constraints, is enabling the extension of model checking procedures based on finite tree automata techniques, in particular for the verification of communicating processes with several local non rewritable memories, like security protocols. Finally, a comparison of RTA with several classes of tree automata with local and global equality tests, with dag automata and Horn clause formalisms is also provided.
Document type :
Journal articles
Complete list of metadata
Contributor : Florent Jacquemard Connect in order to contact the contributor
Submitted on : Wednesday, March 23, 2011 - 7:29:11 AM
Last modification on : Monday, February 15, 2021 - 10:50:18 AM
Long-term archiving on: : Friday, June 24, 2011 - 2:30:52 AM


Files produced by the author(s)



Florent Jacquemard, Francis Klay, Camille Vacher. Rigid Tree Automata and Applications. Information and Computation, Elsevier, 2011, 209 (3), pp.486-512. ⟨10.1016/j.ic.2010.11.015⟩. ⟨inria-00578820⟩



Record views


Files downloads