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 non-deterministic (ND) top-down and ND bottom-up tree automata are equivalent in expressive power, deterministic top-down automata are strictly less powerful than their deterministic bottom-up counterparts, because tree properties specified by deterministic top-down tree automata can only depend on path properties. (Deterministic bottom-up tree automata are as powerful as ND tree automata.)
Read more about Tree Automaton: Definitions
Famous quotes containing the word tree:
“I said I had the tree. It wasn’t true.
The opposite was true. The tree had me.
The minute it was left with me alone,
It caught me up as if I were the fish
And it the fishpole.”
—Robert Frost (1874–1963)