(definition)
Definition: A tree automaton is an extension of a finite state machine, but 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 E. Black.
Entry modified Mon Mar 7 10:05:04 2005.
HTML page formatted Wed Oct 26 09:48:17 2005.
Cite this as:
David Monniaux, "tree automaton", from
Dictionary of Algorithms and Data
Structures, Paul E. Black, ed.,
NIST.
http://www.nist.gov/dads/HTML/treeautomata.html
