Tree stack automaton

It is a finite-state automaton with the additional ability to manipulate a tree-shaped stack.

A restricted class of tree stack automata recognises exactly the languages generated by multiple context-free grammars[3] (or linear context-free rewriting systems).

A tree stack automaton is a 6-tuple A = (Q, Γ, Σ, qi, δ, Qf) where A configuration of A is a tuple (q, c, w) where A transition τ = (q1, u, p, f, q2) is applicable to a configuration (q, c, w) if The transition relation of A is the binary relation ⊢ on configurations of A that is the union of all the relations ⊢τ for a transition τ = (q1, u, p, f, q2) where, whenever τ is applicable to (q, c, w), we have (q, c, w) ⊢τ (q2, f(c), v) and v is obtained from w by removing the prefix u.

The language of A is the set of all words w for which there is some state q ∈ Qf and some tree stack c such that (qi, ci, w) ⊢* (q, c, ε) where Tree stack automata are equivalent to Turing machines.

A tree stack automaton is called k-restricted for some positive natural number k if, during any run of the automaton, any position of the tree stack is accessed at most k times from below.

A tree stack with stack pointer 1.2 and domain { ε , 1, 42, 1.2, 1.5, 1.5.3}
Illustration of the instruction id on a tree stack
Illustration of the instruction push on a tree stack
Illustration of the instructions up and down on a tree stack
Illustration of the instruction set on a tree stack