Tree stack automaton
A tree stack automaton (plural: tree stack automata) is a formalism considered in automata theory. It is a finite state automaton with the additional ability to manipulate a tree-shaped stack. It is an automaton with storage whose storage roughly resembles the configurations of a thread automaton. A restricted class of tree stack automata recognises exactly the languages generated by multiple context-free grammars (or linear context-free rewriting systems). Definition. Tree stack. For a finite and non-empty set , a "tree stack over " is a tuple where The set of all tree stacks over is denoted  by . The set of "predicates" on , denoted by , contains the following unary predicates: for every . The set of "instructions" on , denoted by , contains the following partial functions: for every positive integer and every . Tree stack automata. A "tree stack automaton" is a 6-tuple where A "configuration of " is a tuple where A transition is "applicable" to a configuration if The "transition relation of " is the binary relation on configurations of that is the union of all the relations for a transition where, whenever is applicable to , we have and is obtained from by removing the prefix . The "language of   is the set of all words for which there is some state and some tree stack such that where Related formalisms. Tree stack automata are equivalent to Turing machines. A tree stack automaton is called -restricted" for some positive natural number if, during any run of the automaton, any position of the tree stack is accessed at most times from below. 1-restricted tree stack automata are equivalent to pushdown automata and therefore also to context-free grammars. -restricted tree stack automata are equivalent to linear context-free rewriting systems and multiple context-free grammars of fan-out at most  (for every positive integer ).