A tree stack automaton^[a] (plural: tree stack automata) is aformalism considered inautomata theory. It is afinite-state automaton with the additional ability to manipulate atree-shapedstack. It is an automaton with storage^[2] whose storage roughly resembles the configurations of athread automaton. A restricted class of tree stack automata recognises exactly thelanguages generated by multiplecontext-free grammars^[3] (orlinear context-free rewriting systems).

For a finite and non-empty setΓ, atree stack overΓ is a tuple(t,p) where

• t is apartial function from strings of positive integers to the setΓ ∪ {@} withprefix-closed^[b]domain (calledtree),
• @ (calledbottom symbol) is not inΓ and appears exactly at the root oft, and
• p is an element of the domain oft (calledstack pointer).

The set of all tree stacks overΓ is denoted byTS(Γ).

The set ofpredicates onTS(Γ), denoted byPred(Γ), contains the followingunarypredicates:

• true which is true for any tree stack overΓ,
• bottom which is true for tree stacks whose stack pointer points to the bottom symbol, and
• equals(γ) which is true for some tree stack(t,p) ift(p) =γ,

for everyγ ∈Γ.

The set ofinstructions onTS(Γ), denoted byInstr(Γ), contains the following partial functions:

• id: TS(Γ) → TS(Γ) which is the identity function onTS(Γ),
• push_n,γ: TS(Γ) → TS(Γ) which adds for a given tree stack(t,p) a pair(pn ↦γ) to the treet and sets the stack pointer topn (i.e. it pushesγ to then-th child position) ifpn is not yet in the domain oft,
• up_n: TS(Γ) → TS(Γ) which replaces the current stack pointerp bypn (i.e. it moves the stack pointer to then-th child position) ifpn is in the domain oft,
• down: TS(Γ) → TS(Γ) which removes the last symbol from the stack pointer (i.e. it moves the stack pointer to the parent position), and
• set_γ: TS(Γ) → TS(Γ) which replaces the symbol currently under the stack pointer byγ,

for every positive integern and everyγ ∈Γ.

Atree stack automaton is a 6-tupleA = (Q,Γ,Σ,q_i,δ,Q_f) where

• Q,Γ, andΣ are finite sets (whose elements are calledstates,stack symbols, andinput symbols, respectively),
• q_i ∈Q (theinitial state),
• δ ⊆_fin.Q × (Σ ∪ {ε}) × Pred(Γ) × Instr(Γ) ×Q (whose elements are calledtransitions), and
• Q_f ⊆ TS(Γ) (whose elements are calledfinal states).

Aconfiguration ofA is a tuple(q,c,w) where

• q is a state (thecurrent state),
• c is a tree stack (thecurrent tree stack), and
• w is a word overΣ (theremaining word to be read).

A transitionτ = (q₁,u,p,f,q₂) isapplicable to a configuration(q,c,w) if

• q₁ =q,
• p is true onc,
• f is defined forc, and
• u is a prefix ofw.

Thetransition relation ofA is thebinary relation⊢ on configurations ofA that is the union of all the relations⊢_τ for a transitionτ = (q₁,u,p,f,q₂) where, wheneverτ is applicable to(q,c,w), we have(q,c,w) ⊢_τ (q₂,f(c),v) andv is obtained fromw by removing the prefixu.

Thelanguage ofA is the set of all wordsw for which there is some stateq ∈Q_f and some tree stackc such that(q_i,c_i, w) ⊢^* (q,c,ε) where

• ⊢^* is thereflexive transitive closure of⊢ and
• c_i = (t_i,ε) such thatt_i assigns forε the symbol@ and is undefined otherwise.

Tree stack automata are equivalent toTuring machines.

A tree stack automaton is calledk-restricted for some positive natural numberk if, during any run of the automaton, any position of the tree stack is accessed at mostk times from below.

1-restricted tree stack automata are equivalent topushdown automata and therefore also tocontext-free grammars.k-restricted tree stack automata are equivalent tolinear context-free rewriting systems and multiple context-free grammars of fan-out at mostk (for every positive integerk).^[3]

• Models of computation
• Automata (computation)