(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, 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 6 January 2022.
HTML page formatted Thu Jan 6 17:13:50 2022.
Cite this as:
David Monniaux, "tree automaton", in
Dictionary of Algorithms and Data Structures [online], Paul E. Black, ed. 6 January 2022. (accessed TODAY)
Available from: https://www.nist.gov/dads/HTML/treeAutomaton.html