Visibly Tree Automata with Memory and Constraints

Hubert Comon-Lundh 1 Florent Jacquemard 1, 2 Nicolas Perrin 3, 4
2 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
Abstract : Tree automata with one memory have been introduced in 2001. They generalize both pushdown (word) automata and the tree automata with constraints of equality between brothers of Bogaert and Tison. Though it has a decidable emptiness problem, the main weakness of this model is its lack of good closure properties. We propose a generalization of the visibly pushdown automata of Alur and Madhusudan to a family of tree recognizers which carry along their (bottom-up) computation an auxiliary unbounded memory with a tree structure (instead of a symbol stack). In other words, these recognizers, called Visibly Tree Automata with Memory (VTAM) define a subclass of tree automata with one memory enjoying Boolean closure properties. We show in particular that they can be determinized and the problems like emptiness, membership, inclusion and universality are decidable for VTAM. Moreover, we propose several extensions of VTAM whose transitions may be constrained by different kinds of tests between memories and also constraints a la Bogaert and Tison. We show that some of these classes of constrained VTAM keep the good closure and decidability properties, and we demonstrate their expressiveness with relevant examples of tree languages.
Type de document :
Article dans une revue
Logical Methods in Computer Science, Logical Methods in Computer Science Association, 2008, 4 (2), 〈http://arxiv.org/pdf/0804.3065〉. 〈10.2168/LMCS-4(2:8)2008〉
Liste complète des métadonnées

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

https://hal.inria.fr/inria-00578844
Contributeur : Florent Jacquemard <>
Soumis le : mardi 22 mars 2011 - 14:38:17
Dernière modification le : jeudi 11 janvier 2018 - 06:22:14
Document(s) archivé(s) le : jeudi 23 juin 2011 - 02:45:08

Fichier

VTAM-LMCS.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Citation

Hubert Comon-Lundh, Florent Jacquemard, Nicolas Perrin. Visibly Tree Automata with Memory and Constraints. Logical Methods in Computer Science, Logical Methods in Computer Science Association, 2008, 4 (2), 〈http://arxiv.org/pdf/0804.3065〉. 〈10.2168/LMCS-4(2:8)2008〉. 〈inria-00578844〉

Partager

Métriques

Consultations de la notice

298

Téléchargements de fichiers

165