Tree stack automaton

A tree stack automaton (plural: tree stack automata) is a theoretical device considered in automata theory. It is a finite state automaton with the additional ability to manipulate a tree-shaped stack. A restricted class of tree stack automata recognises exactly the languages generated by multiple context-free grammars^[1] (or linear context-free rewriting systems).

Definition

Tree stack

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

$t$ is a partial function from $ℕ *$ to $Γ \cup {@$ } with prefix-closed^[a] 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 $γ \in Γ$ .

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

$id: TS(Γ) \to TS(Γ)$ which is the identity function on $TS(Γ)$ ,
$push n, γ : TS(Γ) \to TS(Γ)$ which adds for a given tree stack $(t, p)$ a pair $(pn \mapsto γ)$ to the tree $t$ and sets the stack pointer to $pn$ (i.e. it pushes $γ$ to the $n$ -th child position) if $pn$ is not yet in the domain of $t$ ,
$up n : TS(Γ) \to TS(Γ)$ which replaces the current stack pointer $p$ by $pn$ (i.e. it moves the stack pointer to the $n$ -th child position) if $pn$ is in the domain of $t$ ,
$down: TS(Γ) \to TS(Γ)$ which removes the last symbol from the stack pointer (i.e. it moves the stack pointer to the parent position), and
$set γ : TS(Γ) \to TS(Γ)$ which replaces the symbol currently under the stack pointer by $γ$ ,

for every natural number $n$ and every $γ \in Γ$ .

Tree stack automata

A tree stack automaton is a 6-tuple $A = (Q, Γ, Σ, q i, δ, Q f)$ where

$Q$ , $Γ$ , and $Σ$ are finite sets (called states, stack symbols, and input symbols, respectively),
$q i \in Q$ (called initial state),
$δ \subseteq fin. Q \times (Σ \cup {ε}) \times Pred(Γ) \times Instr(Γ) \times Q$ (called set of transitions), and
$Q f \subseteq TS(Γ)$ (called set of 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 \in Q f$ and some tree stack $c$ such that $(q i, c i, w) ⊢ * (q, c, ε)$ where

$⊢ *$ is the transitive closure of $⊢$ and
$c i$ denotes the tree stack with stack pointer $ε$ and the tree that assigns for $ε$ the symbol $@$ and is undefined otherwise.

Notes

^ A set of strings is prefix closed if for every element $w$ in the set, all prefixes of $w$ are also in the set.

References

^ Denkinger, Tobias (2016). An automata characterisation for multiple context-free languages. Proceedings of the 20th International Conference on Developments in Language Theory (DLT 2016). arXiv:1606.02975 [cs.FL].

[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] Denkinger, Tobias (2016). An automata characterisation for multiple context-free languages. Proceedings of the 20th International Conference on Developments in Language Theory (DLT 2016). arXiv:1606.02975 [cs.FL].

[1]

[a]