Tree stack automaton explained

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^[1] 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^[2] (or linear context-free rewriting systems).

Definition

Tree stack

For a finite and non-empty set, a tree stack over is a tuple where

• is a partial function from strings of positive integers to the set with prefix-closed domain (called tree),
• (called bottom symbol) is not in and appears exactly at the root of, and
• is an element of the domain of (called stack pointer).

The set of all tree stacks over is denoted by .

The set of predicates on, denoted by, contains the following unary predicates:

• which is true for any tree stack over,
• which is true for tree stacks whose stack pointer points to the bottom symbol, and
• which is true for some tree stack if,

for every .

The set of instructions on, denoted by, contains the following partial functions:

• which is the identity function on,
• which adds for a given tree stack a pair to the tree and sets the stack pointer to (i.e. it pushes to the -th child position) if is not yet in the domain of,
• which replaces the current stack pointer by (i.e. it moves the stack pointer to the -th child position) if is in the domain of,
• which removes the last symbol from the stack pointer (i.e. it moves the stack pointer to the parent position), and
• which replaces the symbol currently under the stack pointer by,

for every positive integer and every .

Tree stack automata

A tree stack automaton is a 6-tuple where

• ,, and are finite sets (whose elements are called states, stack symbols, and input symbols, respectively),
• (the initial state),
• (whose elements are called transitions), and
• (whose elements are called final states).

A configuration of is a tuple where

• is a state (the current state),
• is a tree stack (the current tree stack), and
• is a word over (the remaining word to be read).

A transition is applicable to a configuration if

• ,
• is true on,
• is defined for, and
• is a prefix of .

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

• is the reflexive transitive closure of and
• such that assigns for the symbol and is undefined otherwise.

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

Notes and References

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