Jump to content

Tree stack automaton

From Wikipedia, the free encyclopedia

This is an old revision of this page, as edited by Tdenk (talk | contribs) at 15:37, 15 June 2016 (added basic definitions and citation). The present address (URL) is a permanent link to this revision, which may differ significantly from the current revision.

(diff) ← Previous revision | Latest revision (diff) | Newer revision → (diff)

This article, Tree stack automaton, has recently been created via the Articles for creation process. Please check to see if the reviewer has accidentally left this template after accepting the draft and take appropriate action as necessary.

Reviewer tools: Inform author

A tree stack automaton (plural: tree stack automata) is a 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

A tree stack over Γ is a tuple $(t, p)$ where

$t$ is a partial function from $ℕ *$ to a finite set $Γ$ with prefix-closed^[a] domain (called tree) 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 is the empty word, and
for every stack symbol $γ$ the predicate $equals(γ)$ which is true for some tree stack $(t, p)$ if $t (p) = γ$ .

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

$id: TS(Γ) \to TS(Γ)$ ,
$push n, γ : TS(Γ) \to TS(Γ)$ ,
$up n : TS(Γ) \to TS(Γ)$ ,
$down: TS(Γ) \to TS(Γ)$ , and
$set γ : TS(Γ) \to TS(Γ)$ .

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 Σ \times Pred(Γ) \times Instr(Γ) \times Q$ (called set of transitions), and
$Q f \subseteq TS(Γ)$ (called set of final states).

Example

Restricted tree stack automata

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

Retrieved from "https://en.wikipedia.org/w/index.php?title=Tree_stack_automaton&oldid=725424270"