Tree automaton

Summary

A tree automaton is a finite automaton that reads finite labelled trees, such as terms or syntax trees, instead of words. A bottom-up tree automaton assigns states to the leaves, and then to each node from the states of its children. It accepts when the root gets an accepting state. The tree languages recognized in this way, the regular tree languages, keep most good properties of regular languages of words. Tree automata are used for XML schemas, term rewriting, program analysis and decision procedures in logic.