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. 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, and in fact the class of indexed languages is exactly the class of languages accepted by one-way nondeterministic nested stack automata.
See also 
- ^ 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.