ART

In automata theory, a nested stack automaton is a finite automaton that can make use of a stack containing data which can be additional stacks.[1] Like a stack automaton, a nested stack automaton may step up or down in the stack, and read the current symbol; in addition, it may at any place create a new stack, operate on that one, eventually destroy it, and continue operating on the old stack. This way, stacks can be nested recursively to an arbitrary depth; however, the automaton always operates on the innermost stack only.

A nested stack automaton is capable of recognizing an indexed language,[2] and in fact the class of indexed languages is exactly the class of languages accepted by one-way nondeterministic nested stack automata.[1][3]

Nested stack automata should not be confused with embedded pushdown automata, which have less computational power.

Formal definition
Automaton

      Q × Σ' × [Γ into subsets of Q × D × [Γ* (pushdown mode),
Q × Σ' × Γ' into subsets of Q × D × D (reading mode),
Q × Σ' × [Γ' into subsets of Q × D × {+1} (reading mode),
Q × Σ' × {]} into subsets of Q × D × {-1} (reading mode),
Q × Σ' × (Γ' ∪ [Γ') into subsets of Q × D × [Γ*] (stack creation mode), and
Q × Σ' × {[]} into subsets of Q × D × {ε}, (stack destruction mode),
Informally, the top symbol of a (sub)stack together with its preceding left endmarker "[" is viewed as a single symbol;[4] then δ reads
  • the current state,
  • the current input symbol, and
  • the current stack symbol,
and outputs
  • the next state,
  • the direction in which to move on the input, and
  • the direction in which to move on the stack, or the string of symbols to replace the topmost stack symbol.

Configuration

A configuration, or instantaneous description of such an automaton consists in a triple ⟨ q, [a1a2...ai...an-1], [Z1X2...Xj...Xm-1] ⟩, where

q ∈ Q is the current state,
[a1a2...ai...an-1] is the input string; for convenience, a0 = [ and an = ] is defined[note 3] The current position in the input, viz. i with 0 ≤ i ≤ n, is marked by underlining the respective symbol.
[Z1X2...Xj...Xm-1] is the stack, including substacks; for convenience, X1 = [Z1 [note 4] and Xm = ] is defined. The current position in the stack, viz. j with 1 ≤ j ≤ m, is marked by underlining the respective symbol.

Example

An example run (input string not shown):

Action Step Stack
1:       [a b [k ] [p ] c ]  
create substack       2: [a b [k ] [p [r s ] ] c ]
pop 3: [a b [k ] [p [s ] ] c ]  
pop 4: [a b [k ] [p [] ] c ]  
destroy substack 5: [a b [k ] [p ] c ]  
move down 6: [a b [k ] [p ] c ]  
move up 7: [a b [k ] [p ] c ]  
move up 8: [a b [k ] [p ] c ]  
push 9: [a b [k ] [n o p ] c ]  

Properties

When automata are allowed to re-read their input ("two-way automata"), nested stacks do not result in additional language recognition capabilities, compared to plain stacks.[5]

Gilman and Shapiro used nested stack automata to solve the word problem in certain groups.[6]
Notes

Aho originally used "$", "¢", and "#" instead of "[", "]", and "]", respectively. See Aho (1969), p.385 top.
Juxataposition denotes string (set) concatenation, and has a higher binding priority than set union ∪. For example, [Γ' denotes the set of all length-2 strings starting with "[" and ending with a symbol from Γ'.
Aho originally used the left and right stack marker, viz. $ and ¢, as right and left input marker, respectively.

The top symbol of a (sub)stack together with its preceding left endmarker "[" is viewed as a single symbol.

References

Aho, Alfred V. (July 1969). "Nested Stack Automata". Journal of the ACM. 16 (3): 383–406. doi:10.1145/321526.321529. S2CID 685569.
Partee, Barbara; Alice ter Meulen; Robert E. Wall (1990). Mathematical Methods in Linguistics. Kluwer Academic Publishers. pp. 536–542. ISBN 978-90-277-2245-4.
John E. Hopcroft, Jeffrey D. Ullman (1979). Introduction to Automata Theory, Languages, and Computation. Addison-Wesley. ISBN 0-201-02988-X. Here:p.390
Aho (1969), p.385 top
Beeri, C. (June 1975). "Two-way nested stack automata are equivalent to two-way stack automata". Journal of Computer and System Sciences. 10 (3): 317–339. doi:10.1016/s0022-0000(75)80004-3.

Shapiro, Robert Gilman Michael (4 December 1998). On groups whose word problem is solved by a nested stack automaton (Technical report). arXiv:math/9812028. CiteSeerX 10.1.1.236.2029. S2CID 12716492.

Automata theory: formal languages and formal grammars
Chomsky hierarchy Grammars Languages Abstract machines
  • Type-0
  • Type-1
  • Type-2
  • Type-3
  • Unrestricted
  • (no common name)
  • Context-sensitive
  • Positive range concatenation
  • Indexed
  • Linear context-free rewriting systems
  • Tree-adjoining
  • Context-free
  • Deterministic context-free
  • Visibly pushdown
  • Regular
  • Non-recursive
  • Recursively enumerable
  • Decidable
  • Context-sensitive
  • Positive range concatenation*
  • Indexed*
  • Linear context-free rewriting language
  • Tree-adjoining
  • Context-free
  • Deterministic context-free
  • Visibly pushdown
  • Regular
  • Star-free
  • Finite
  • Turing machine
  • Decider
  • Linear-bounded
  • PTIME Turing Machine
  • Nested stack
  • Thread automaton
  • restricted Tree stack automaton
  • Embedded pushdown
  • Nondeterministic pushdown
  • Deterministic pushdown
  • Visibly pushdown
  • Finite
  • Counter-free (with aperiodic finite monoid)
  • Acyclic finite
Each category of languages, except those marked by a *, is a proper subset of the category directly above it. Any language in each category is generated by a grammar and by an automaton in the category in the same line.

Undergraduate Texts in Mathematics

Graduate Texts in Mathematics

Graduate Studies in Mathematics

Mathematics Encyclopedia

World

Index

Hellenica World - Scientific Library

Retrieved from "http://en.wikipedia.org/"
All text is available under the terms of the GNU Free Documentation License