×

Alternating pushdown and stack automata. (English) Zbl 0538.68039

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

MSC:

68Q05 Models of computation (Turing machines, etc.) (MSC2010)
68Q25 Analysis of algorithms and problem complexity
68Q45 Formal languages and automata
PDF BibTeX XML Cite
Full Text: DOI