Ladner, Richard E.; Lipton, Richard J.; Stockmeyer, Larry J. Alternating pushdown and stack automata. (English) Zbl 0538.68039 SIAM J. Comput. 13, 135-155 (1984). The power of 2-way pushdown, stack and nonerasing stack automata with and without an additional (auxiliary) space bounded worktape is characterized in terms of time complexity classes of deterministic Turing machines. Reviewer: G.Wechsung Cited in 42 Documents MSC: 68Q05 Models of computation (Turing machines, etc.) (MSC2010) 68Q25 Analysis of algorithms and problem complexity 68Q45 Formal languages and automata Keywords:pushdown automata; stack automata; 2-way finite state automata; nonerasing stack; time complexity classes; deterministic Turing machines PDF BibTeX XML Cite \textit{R. E. Ladner} et al., SIAM J. Comput. 13, 135--155 (1984; Zbl 0538.68039) Full Text: DOI OpenURL