| |
VOLUME 4, ISSUE 2, PAPER 8
|
Visibly Tree Automata with Memory and Constraints
|
©Hubert Comon-Lundh, LSV & ENS Cachan
©Florent Jacquemard, INRIA Futurs & LSV
©Nicolas Perrin, ENS Lyon
|
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 comparing brother subtrees in the tree
in input. 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.
|
Publication date: June 18, 2008
Full Text: PDF | PostScript
DOI: 10.2168/LMCS-4(2:8)2008
Hit Counts: 2508 |
 Creative Commons | |
