Tree stack automaton

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 storageScott, 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
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 grammarsDenkinger, 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
(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

References

{{Formal languages and grammars
Models of computation
Automata (computation)