Tree stack automaton
A tree stack automaton{{efn|not to be confused with a device with the same name introduced in 1990 by Wolfgang Golubski and Wolfram-M. Lippe 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, [http://www.dx.doi.org/10.1007/BFb0029624 doi:10.1007/BFb0029624].}} (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, [http://www.dx.doi.org/10.1016/s0022-0000(67)80014-x 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, [https://link.springer.com/chapter/10.1007/978-3-662-53132-7_12 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 {{math|Γ}}, a tree stack over {{math|{{var|Γ}}}} is a tuple {{math|(t, p)}} where
- {{math|t}} is a partial function from strings of positive integers to the set {{math|Γ ∪ {@}}} with prefix-closed{{efn|A set of strings is prefix-closed if for every element {{math|w}} in the set, all prefixes of {{math|w}} are also in the set.}} domain (called tree),
- {{math|@}} (called bottom symbol) is not in {{math|Γ}} and appears exactly at the root of {{math|t}}, and
- {{math|p}} is an element of the domain of {{math|t}} (called stack pointer).
The set of all tree stacks over {{math|Γ}} is denoted by {{math|TS(Γ)}}.
The set of predicates on {{math|TS(Γ)}}, denoted by {{math|Pred(Γ)}}, contains the following unary predicates:
- {{math|true}} which is true for any tree stack over {{math|Γ}},
- {{math|bottom}} which is true for tree stacks whose stack pointer points to the bottom symbol, and
- {{math|equals(γ)}} which is true for some tree stack {{math|(t, p)}} if {{math|t(p) {{=}} γ}},
for every {{math|γ ∈ Γ}}.
The set of instructions on {{math|TS(Γ)}}, denoted by {{math|Instr(Γ)}}, contains the following partial functions:
- {{math|id: TS(Γ) → TS(Γ)}} which is the identity function on {{math|TS(Γ)}},
- {{math|pushn,γ: TS(Γ) → TS(Γ)}} which adds for a given tree stack {{math|(t,p)}} a pair {{math|(pn ↦ γ)}} to the tree {{math|t}} and sets the stack pointer to {{math|pn}} (i.e. it pushes {{math|γ}} to the {{math|n}}-th child position) if {{math|pn}} is not yet in the domain of {{math|t}},
- {{math|upn: TS(Γ) → TS(Γ)}} which replaces the current stack pointer {{math|p}} by {{math|pn}} (i.e. it moves the stack pointer to the {{math|n}}-th child position) if {{math|pn}} is in the domain of {{math|t}},
- {{math|down: TS(Γ) → TS(Γ)}} which removes the last symbol from the stack pointer (i.e. it moves the stack pointer to the parent position), and
- {{math|setγ: TS(Γ) → TS(Γ)}} which replaces the symbol currently under the stack pointer by {{math|γ}},
for every positive integer {{math|n}} and every {{math|γ ∈ Γ}}.
| style="margin: 0 auto;"
| File:Push on a tree stack.svg |
=Tree stack automata=
A tree stack automaton is a 6-tuple {{math|A {{=}} (Q, Γ, Σ, qi, δ, Qf)}} where
- {{math|Q}}, {{math|Γ}}, and {{math|Σ}} are finite sets (whose elements are called states, stack symbols, and input symbols, respectively),
- {{math|qi ∈ Q}} (the initial state),
- {{math|δ ⊆fin. Q × (Σ ∪ {ε}) × Pred(Γ) × Instr(Γ) × Q}} (whose elements are called transitions), and
- {{math|Qf ⊆ TS(Γ)}} (whose elements are called final states).
A configuration of {{math|{{var|A}}}} is a tuple {{math|(q, c, w)}} where
- {{math|q}} is a state (the current state),
- {{math|c}} is a tree stack (the current tree stack), and
- {{math|w}} is a word over {{math|Σ}} (the remaining word to be read).
A transition {{math|τ {{=}} (q1, u, p, f, q2)}} is applicable to a configuration {{math|(q, c, w)}} if
- {{math|q1 {{=}} q}},
- {{math|p}} is true on {{math|c}},
- {{math|f}} is defined for {{math|c}}, and
- {{math|u}} is a prefix of {{math|w}}.
The transition relation of {{math|{{var|A}}}} is the binary relation {{math|⊢}} on configurations of {{math|{{var|A}}}} that is the union of all the relations {{math|⊢τ}} for a transition {{math|τ {{=}} (q1, u, p, f, q2)}} where, whenever {{math|τ}} is applicable to {{math|(q, c, w)}}, we have {{math|(q, c, w) ⊢τ (q2, f(c), v)}} and {{math|v}} is obtained from {{math|w}} by removing the prefix {{math|u}}.
The language of {{math|{{var|A}}}} is the set of all words {{math|w}} for which there is some state {{math|q ∈ Qf}} and some tree stack {{math|c}} such that {{math|(qi, ci, w) ⊢* (q, c, ε)}} where
- {{math|⊢*}} is the reflexive transitive closure of {{math|⊢}} and
- {{math|ci {{=}} (ti, ε)}} such that {{math|ti}} assigns for {{math|ε}} the symbol {{math|@}} and is undefined otherwise.
Related formalisms
Tree stack automata are equivalent to Turing machines.
A tree stack automaton is called {{math|{{var|k}}}}-restricted for some positive natural number {{math|{{var|k}}}} if, during any run of the automaton, any position of the tree stack is accessed at most {{math|k}} times from below.
1-restricted tree stack automata are equivalent to pushdown automata and therefore also to context-free grammars.
{{math|k}}-restricted tree stack automata are equivalent to linear context-free rewriting systems and multiple context-free grammars of fan-out at most {{math|k}} (for every positive integer {{math|k}}).
Notes
{{notelist}}