Tree pushdown automata

摘要

This paper presents a new type of automaton called a tree pushdown automaton (a bottom-up tree automaton augmented with internal memory in the form of a tree, similar to the way a stack is added to a finite state machine to produce a pushdown automaton) and shows that the class of languages recognized by such automata is identical to the class of context-free tree languages.