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,Δ)
Full article ▸
