Tree stack automaton
A tree stack automaton^{[loweralpha 1]} (plural: tree stack automata) is a formalism considered in automata theory. It is a finite state automaton with the additional ability to manipulate a treeshaped stack. It is an automaton with storage^{[2]} whose storage roughly resembles the configurations of a thread automaton. A restricted class of tree stack automata recognises exactly the languages generated by multiple contextfree grammars^{[3]} (or linear contextfree rewriting systems).
Definition
Tree stack
For a finite and nonempty set Γ, a tree stack over Γ is a tuple (t, p) where
 t is a partial function from strings of positive integers to the set Γ ∪ {@} with prefixclosed^{[loweralpha 2]} domain (called tree),
 @ (called bottom symbol) is not in Γ and appears exactly at the root of t, and
 p is an element of the domain of t (called stack pointer).
The set of all tree stacks over Γ is denoted by TS(Γ).
The set of predicates on TS(Γ), denoted by Pred(Γ), contains the following unary predicates:
 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) if t(p) = γ,
for every γ ∈ Γ.
The set of instructions on TS(Γ), denoted by Instr(Γ), contains the following partial functions:
 id: TS(Γ) → TS(Γ) which is the identity function on TS(Γ),
 push_{n,γ}: TS(Γ) → TS(Γ) which adds for a given tree stack (t,p) a pair (pn ↦ γ) to the tree t and sets the stack pointer to pn (i.e. it pushes γ to the nth child position) if pn is not yet in the domain of t,
 up_{n}: TS(Γ) → TS(Γ) which replaces the current stack pointer p by pn (i.e. it moves the stack pointer to the nth child position) if pn is in the domain of t,
 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 integer n and every γ ∈ Γ.




Tree stack automata
A tree stack automaton is a 6tuple A = (Q, Γ, Σ, q_{i}, δ, Q_{f}) where
 Q, Γ, and Σ are finite sets (whose elements are called states, stack symbols, and input symbols, respectively),
 q_{i} ∈ Q (the initial state),
 δ ⊆_{fin.} Q × (Σ ∪ {ε}) × Pred(Γ) × Instr(Γ) × Q (whose elements are called transitions), and
 Q_{f} ⊆ TS(Γ) (whose elements are called final states).
A configuration of A is a tuple (q, c, w) where
 q is a state (the current state),
 c is a tree stack (the current tree stack), and
 w is a word over Σ (the remaining word to be read).
A transition τ = (q_{1}, u, p, f, q_{2}) is applicable to a configuration (q, c, w) if
 q_{1} = q,
 p is true on c, and
 f is defined for c.
The transition relation of A is the binary relation ⊢ on configurations of A that is the union of all the relations ⊢_{τ} for a transition τ = (q_{1}, u, p, f, q_{2}) where, whenever τ is applicable to (q, c, w), we have (q, c, w) ⊢_{τ} (q_{2}, 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 ∈ Q_{f} and some tree stack c such that (q_{i}, c_{i}, w) ⊢^{*} (q, c, ε) where
 ⊢^{*} is the reflexive transitive closure of ⊢ and
 c_{i} = (t_{i}, ε) such that t_{i} assigns for ε the symbol @ and is undefined otherwise.
Related formalisms
Tree stack automata are equivalent to Turing machines.
A tree stack automaton is called krestricted 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.
1restricted tree stack automata are equivalent to pushdown automata and therefore also to contextfree grammars. krestricted tree stack automata are equivalent to linear contextfree rewriting systems and multiple contextfree grammars of fanout at most k (for every positive integer k).^{[3]}
Notes
References
 ↑ Golubski, Wolfgang and Lippe, WolframM. (1990). Treestack automata. Proceedings of the 15th Symposium on Mathematical Foundations of Computer Science (MFCS 1990). Lecture Notes in Computer Science, Vol. 452, pages 313–321, doi:10.1007/BFb0029624.
 ↑ Scott, Dana (1967). Some Definitional Suggestions for Automata Theory. Journal of Computer and System Sciences, Vol. 1(2), pages 187–212, doi:10.1016/s00220000(67)80014x.
 1 2 Denkinger, Tobias (2016). An automata characterisation for multiple contextfree languages. Proceedings of the 20th International Conference on Developments in Language Theory (DLT 2016). Lecture Notes in Computer Science, Vol. 9840, pages 138–150, doi:10.1007/9783662531327_12.