(definition)
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.
Author: DM
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 Feb 2 13:10:40 2015.
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