Subhash Khot, Richard J. Lipton, et al.
Algorithmica (New York)
Languages accepted by alternating auxiliary pushdown automata using simultaneously a(n) alternations and s(n) space are shown to be members of the class of languages accepted by nondeterministic Turing machines using a(n) 2es(n) space for some c > 0. This result is used to show that the hierarchy of classes of languages accepted by pushdown automata based on the number of alternations collapses at the second level of the hierarchy. The power of alternation bounded pushdown automata without auxiliary storage is also investigated. © 1984 Academic Press, Inc.
Subhash Khot, Richard J. Lipton, et al.
Algorithmica (New York)
Richard J. Lipton
FOCS 1975
Richard J. Lipton, Larry J. Stockmeyer
Journal of Computer and System Sciences
Larry J. Stockmeyer, Vijay V. Vazirani
Information Processing Letters