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] A nested stack automaton may read its stack, in addition to pushing or popping it. 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] 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.[3]
Gilman and Shapiro used nested stack automata to solve the word problem in certain groups.[4]
See also
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) - ^ 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. |