Tree stack automaton

A tree stack automaton[lower-alpha 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 tree-shaped 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 context-free grammars[3] (or linear context-free rewriting systems).


Tree stack

A tree stack with stack pointer 1.2 and domain {ε, 1, 42, 1.2, 1.5, 1.5.3}

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

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:

for every γΓ.

The set of instructions on TS(Γ), denoted by Instr(Γ), contains the following partial functions:

for every positive integer n and every γΓ.

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

Tree stack automata

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 qQf and some tree stack c such that (qi, ci, w) ⊢* (q, c, ε) where

Related formalisms

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.

1-restricted tree stack automata are equivalent to pushdown automata and therefore also to context-free grammars. k-restricted tree stack automata are equivalent to linear context-free rewriting systems and multiple context-free grammars of fan-out at most k (for every positive integer k).[3]


  1. not to be confused with a device with the same name introduced in 1990 by Wolfgang Golubski and Wolfram-M. Lippe [1]
  2. A set of strings is prefix-closed if for every element w in the set, all prefixes of w are also in the set.


  1. Golubski, Wolfgang and Lippe, Wolfram-M. (1990). Tree-stack 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.
  2. Scott, Dana (1967). Some Definitional Suggestions for Automata Theory. Journal of Computer and System Sciences, Vol. 1(2), pages 187–212, doi:10.1016/s0022-0000(67)80014-x.
  3. 1 2 Denkinger, Tobias (2016). An automata characterisation for multiple context-free 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/978-3-662-53132-7_12.

This article is issued from Wikipedia - version of the 10/5/2016. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.