Definition: An extension of a finite state machine that operates on n-ary constructors. Where a finite state automaton reaches a new state with a single state and character, a tree automaton takes n states and constructors. Tree automata may be top-down (starting from the root) or bottom-up (starting from the leaves), and deterministic or nondeterministic.
See also deterministic finite tree automaton, nondeterministic finite tree automaton, deterministic tree automaton, nondeterministic tree automaton, bottom-up tree automaton, top-down tree automaton.
Note: Words for finite state automata can be seen as composed of unary constructors, the alphabet, and a 0-ary constructor, the end of the word.
Nondeterministic top-down and bottom-up automata, and deterministic bottom-up automata are equivalent, but top-down automata are weaker.
Tree Automata Techniques and Applications page.
If you have suggestions, corrections, or comments, please get in touch with Paul Black.
Entry modified 22 October 2007.
HTML page formatted Mon Nov 18 10:44:10 2013.
Cite this as:
David Monniaux, "tree automaton", in Dictionary of Algorithms and Data Structures [online], Vreda Pieterse and Paul E. Black, eds. 22 October 2007. (accessed TODAY) Available from: http://www.nist.gov/dads/HTML/treeAutomaton.html