NIST

tree automaton

(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

More information

Tree Automata Techniques and Applications page.


Go to the Dictionary of Algorithms and Data Structures home 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