Rigid Tree Automata

Florent Jacquemard 1 Francis Klay 2 Camille Vacher 3, 4
1 DAHU - Verification in databases
LSV - Laboratoire Spécification et Vérification [Cachan], ENS Cachan - École normale supérieure - Cachan, Inria Saclay - Ile de France, CNRS - Centre National de la Recherche Scientifique : UMR8643
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 restricted disequality tests as well. Properties like determinism, 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 a RTA language under a restricted family of term rewriting systems, whereas this closure is not a 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. Finally, a comparison of RTA with several classes of tree automata with local and global equality tests, and with dag automata is also provided.
Type de document :
Communication dans un congrès
Adrian Horia Dediu and Armand Mihai Ionescu and Carlos Martín-Vide. Third International Conference on Language and Automata Theory and Applications, Apr 2009, Tarragona, Spain. Springer, 5457, pp.446-457, 2009, Lecture Notes in Computer Science. 〈http://www.springerlink.com/content/m381707kkqh12401/〉. 〈10.1007/978-3-642-00982-2_38〉
Liste complète des métadonnées

Littérature citée [16 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/inria-00579001
Contributeur : Florent Jacquemard <>
Soumis le : mardi 22 mars 2011 - 20:48:09
Dernière modification le : jeudi 11 janvier 2018 - 06:22:14
Document(s) archivé(s) le : jeudi 23 juin 2011 - 02:57:46

Fichier

RTA.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Collections

Citation

Florent Jacquemard, Francis Klay, Camille Vacher. Rigid Tree Automata. Adrian Horia Dediu and Armand Mihai Ionescu and Carlos Martín-Vide. Third International Conference on Language and Automata Theory and Applications, Apr 2009, Tarragona, Spain. Springer, 5457, pp.446-457, 2009, Lecture Notes in Computer Science. 〈http://www.springerlink.com/content/m381707kkqh12401/〉. 〈10.1007/978-3-642-00982-2_38〉. 〈inria-00579001〉

Partager

Métriques

Consultations de la notice

350

Téléchargements de fichiers

160