automata theory, a nested stack automaton is a finite automaton that can make use of a stack containing data which can be additional stacks. A nested stack automaton may read its stack, in addition to pushing or popping it. A nested stack automaton is capable of recognizing an [1 ] indexed language, and in fact the class of indexed languages is exactly the class of languages accepted by one-way [2 ] nondeterministic nested stack automata. Nested stack automata should not be confused with [1 ] embedded pushdown automata, which have less computational power. [ ] citation needed
Properties [ edit ]
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 [ edit ]
References [ edit ]
^ 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; Alice ter Meulen, and Robert E. Wall (1990). Mathematical Methods in Linguistics. Kluwer Academic Publishers. pp. 536–542. ISBN 978-90-277-2245-4.
^ C. Beeri (1975). "Two-Way Nested Stack Automata Are Equivalent to Two-Way Stack Automata". J. Comp. and System Sciences 10: 317–339.
^ Robert Gilman, Michael Shapiro (Dec 1998). (Technical report). arXiv. p. 16. On Groups Whose Word Problem is Solved by a Nested Stack Automaton