 Tree automaton

A tree automaton is a type of state machine. Tree automata deal with tree structures, rather than the strings of more conventional state machines.
The following article deals with branching tree automata, which correspond to regular languages of trees. For a different notion of tree automaton, see tree walking automaton.
As with classical automata, finite tree automata (FTA) can be either a deterministic automaton or not. According to how the automaton processes the input tree, finite tree automata can be of two types: (a) bottom up, (b) top down. This is an important issue, as although nondeterministic (ND) topdown and ND bottomup tree automata are equivalent in expressive power, deterministic topdown automata are strictly less powerful than their deterministic bottomup counterparts, because tree properties specified by deterministic topdown tree automata can only depend on path properties. (Deterministic bottomup tree automata are as powerful as ND tree automata.)
Contents
Definitions
A ranked alphabet is a pair of ordinary alphabet and a function . Each letter has its arity so it can be used to build terms. Nullary elements (of zero arity) are also called constants. Terms built with unary symbols and constants can be considered as strings. Higher arity leads to trees.
A bottomup finite tree automaton over F is defined by: (Q,F,Q_{f},Δ)
Here Q is a set of unary letters (states), F is a ranked alphabet, is a set of final states, and Δ is a set of transition rules, that is, rewrite rules from nodes whose childs' roots are states, to nodes whose roots are states. Thus the state of a node is deduced from the states of its children.
There is no initial state as such, but the transition rules for constant symbols (leaves) can be considered as initial states. The tree is accepted if the state labeled at the root is an accepting state.
A topdown finite tree automaton over F is defined by: (Q,F,I,Δ)
There are two differences with bottomup tree automata : first, , the set of its initial states, replaces Q_{F} ; second, its transition rules are the converse, that is, rewrite rules from nodes whose roots are states to nodes whose child's roots are states. The tree is accepted if every branch can be gone through this way.
The rewrite rules cause symbols from Q to 'travel' along branches of the tree.
One can easily guess that nondeterministic topdown tree automata are equivalent to nondeterministic bottomup ones ; the transition rules are simply reversed, and the final states become the initial states.
Why then are deterministic topdown FTA less powerful than their bottomup counterparts? Because a deterministic TA is by definition one where no two transition rules have the same lefthand side. For tree automata, transition rules are rewrite rules ; and for topdown ones, the lefthand side will be parent nodes. Consequently a deterministic topdown tree automaton will only be able to test for tree properties that are true in all branches, because the choice of the state to write into each child branch is determined at the parent node, without knowing the child branches contents.
Properties
Determinism
As said before, a deterministic tree automaton is one where no two transition rules have the same lefthand side. This definition matches the intuitive idea that for an automaton to be deterministic, one and only one transition must be possible for a given node.
Recognizability
For a bottomup automaton, a ground term t (that is, a tree) is accepted if there exists a reduction that starts from t and ends with q(t), where q is a final state. For a topdown automaton, a ground term t is accepted if there exists a reduction that starts from q(t) and ends with t, where q(t) is an initial state.
The tree language L(A) recognized by a tree automaton A is the set of all ground terms accepted by A. A set of ground terms is recognizable if there exists a tree automaton that recognizes it.
One important property is that linear (that is, aritypreserving) homomorphisms preserve recognizability.
Completeness and Reduction
A nondeterministic finite tree automaton is complete if there is at least one transition rule available for every possible symbolstates combination. A state q is accessible if there exists a ground term t such that there exists a reduction from t to q(t). An FTA is reduced if all its states are accessible.
Pumping Lemma
Let L be a recognizable set of ground terms. Then, there exists a constant k > 0 satisfying: for every ground term t in L such that Height(t) > k, there exists a context , a non trivial context and a ground term u such that t = C[C'[u]] and, for all .
Closure
The class of recognizable tree languages is closed under union, under complementation, and under intersection.
MyhillNerode Theorem
A congruence on tree languages is a relation such that
It is of finite index if its number of equivalenceclasses is finite.
For a given treelanguage L, define if for all contexts , .
The MyhillNerode Theorem for tree automaton states that the following three statements are equivalent:
 L is a recognizable tree language
 L is the union of some equivalence classes of congruence of finite index
 the relation is a congruence of finite index
External links
All the information in this page was taken from Chapter 1 of http://tata.gforge.inria.fr
Implementations
(OCaml) Grappa  Ranked and Unranked Tree Automata Libraries (http://www.grappa.univlille3.fr/~filiot/tata/)
(OCaml) Timbuk  Tools for Reachability Analysis and Tree Automata Calculations (http://www.irisa.fr/celtique/genet/timbuk/)
(Java) LETHAL  Library for working with finite tree and hedge automata (http://lethal.sf.net/)
(Isabelle [OCaml, SML, Haskell])  MachineChecked Tree Automata Library (http://afp.sourceforge.net/entries/TreeAutomata.shtml)
(C++) VATA: A Library for Efficient Manipulation of NonDeterministic Tree Automata  (http://www.fit.vutbr.cz/research/groups/verifit/tools/libvata/)
Categories: Trees (structure)
 Automata theory
Wikimedia Foundation. 2010.
См. также в других словарях:
Tree walking automaton — A tree walking automaton (TWA) is a type of finite automaton that deals with tree structures rather than strings.The following article deals with tree walking automata. For a different notion of tree automaton, closely related to regular tree… … Wikipedia
Treeadjoining grammar — (TAG) is a grammar formalism defined by Aravind Joshi. Tree adjoining grammars are somewhat similar to context free grammars, but the elementary unit of rewriting is the tree rather than the symbol. Whereas context free grammars have rules for… … Wikipedia
Automaton — This article is about a self operating machine. For other uses of Automaton, see Automaton (disambiguation) or Automata (disambiguation). An automaton (plural: automata or automatons ) is a self operating machine. The word is sometimes used to… … Wikipedia
Pebble automaton — A pebble automaton is an extension of tree walking automata which allows the automaton to use a finite amount of pebbles , used for marking tree node. The result is a model stronger than ordinary tree walking automata, but still strictly weaker… … Wikipedia
Deterministic pushdown automaton — In automata theory, a pushdown automaton is a finite automaton with an additional stack of symbols; its transitions can take the top symbol on the stack and depend on its value, and they can add new top symbols to the stack. A deterministic… … Wikipedia
Alternating finite automaton — In automata theory, an alternating finite automaton (AFA) is a nondeterministic finite automaton whose transitions are divided into existential and universal transitions. For example, let A be an alternating automaton.* For an existential… … Wikipedia
Nested stack automaton — In automata theory, a nested stack automaton is a finite automaton that can make use of a stack containing data which can be additional stacks.[1] A nested stack automaton may read its stack, in addition to pushing or popping it. A nested stack… … Wikipedia
Deterministic automaton — is a concept of automata theory in which the outcome of a transition from one state to another given a certain input can be predicted for every occurrence. A common deterministic automaton is a deterministic finite state machine (sometimes… … Wikipedia
Büchi automaton — A Büchi automaton is the extension of a finite state automaton to infinite inputs. It accepts an infinite input sequence iff there exists a run of the automaton (in case of a deterministic automaton, there is exactly one possible run) which… … Wikipedia
Embedded pushdown automaton — An embedded pushdown automaton or EPDA is a computational model that parse languages in the tree adjoining grammar (TAG). It is similar to the context free grammar parsing pushdown automaton, except that instead of using a stack (data structure)… … Wikipedia