inria-00579009, version 1
Tree Automata with Memory, Visibility and Structural Constraints
Hubert Comon-Lundh
a, 1Florent Jacquemard
2Nicolas Perrin
3, 4
10th International Conference on Foundations of Software Science and Computation Structures (FOSSACS) 4423 (2007) 168-182
Résumé : 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, inclusion and universality are decidable for VTAM. Moreover, we propose an extension of VTAM whose transitions may be constrained by structural equality and disequality tests between memories, and show that this extension preserves the good closure and decidability properties.
- a – École normale supérieure de Cachan - ENS Cachan
- 1 : Laboratoire Spécification et Vérification [Cachan] (LSV)
- CNRS : UMR8643 – INRIA – École normale supérieure de Cachan - ENS Cachan
- 2 : DAHU (INRIA Saclay - Ile de France)
- INRIA – Ecole Nationale Supérieure de Cachan – CNRS : UMR8643
- 3 : Laboratoire d'analyse et d'architecture des systèmes (LAAS)
- CNRS : UPR8001 – Université Paul Sabatier [UPS] - Toulouse III – Institut National Polytechnique de Toulouse - INPT – Institut National des Sciences Appliquées (INSA) - Toulouse
- 4 : Joint Robotics Laboratory AIST & CNRS (JRL)
- AIST – CNRS : UMI3218
- Domaine : Informatique/Logique en informatique
- inria-00579009, version 1
- http://hal.inria.fr/inria-00579009
- oai:hal.inria.fr:inria-00579009
- Contributeur : Florent Jacquemard
- Soumis le : Mardi 22 Mars 2011, 22:33:57
- Dernière modification le : Mercredi 23 Mars 2011, 10:13:59






Documents associés
Exporter