Nested stack automaton

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.^{[citation needed]}

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.^[4]

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

References

^ ^a ^b Aho, Alfred (1969). "Nested stack automata". Journal of the ACM. 16 (3): 383–406. doi:10.1145/321526.321529. ISSN 0004-5411.
^ Partee, Barbara (1990). Mathematical Methods in Linguistics. Kluwer Academic Publishers. pp. 536–542. ISBN 978-90-277-2245-4. {{cite book}}: Unknown parameter |coauthors= ignored (|author= suggested) (help)
^ John E. Hopcroft, Jeffrey D. Ullman (1979). Introduction to Automata Theory, Languages, and Computation. Addison-Wesley. ISBN 0-201-02988-X. Here:p.390
^ C. Beeri (1975). "Two-Way Nested Stack Automata Are Equivalent to Two-Way Stack Automata" (PDF). J. Comp. and System Sciences. 10: 317–339.
^ Robert Gilman, Michael Shapiro (Dec 1998). On Groups Whose Word Problem is Solved by a Nested Stack Automaton (PDF) (Technical report). arXiv. p. 16.

This computer science article is a stub. You can help Wikipedia by expanding it.

[aho-1] Aho, Alfred (1969). "Nested stack automata". Journal of the ACM. 16 (3): 383–406. doi:10.1145/321526.321529. ISSN 0004-5411.

[2] Partee, Barbara (1990). Mathematical Methods in Linguistics. Kluwer Academic Publishers. pp. 536–542. ISBN 978-90-277-2245-4. {{cite book}}: Unknown parameter |coauthors= ignored (|author= suggested) (help)

[3] John E. Hopcroft, Jeffrey D. Ullman (1979). Introduction to Automata Theory, Languages, and Computation. Addison-Wesley. ISBN 0-201-02988-X. Here:p.390

[4] C. Beeri (1975). "Two-Way Nested Stack Automata Are Equivalent to Two-Way Stack Automata" (PDF). J. Comp. and System Sciences. 10: 317–339.

[5] Robert Gilman, Michael Shapiro (Dec 1998). On Groups Whose Word Problem is Solved by a Nested Stack Automaton (PDF) (Technical report). arXiv. p. 16.

[1]

[2]

[3]

[4]

[5]

Properties

See also

References