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 ).