Alternation bounded auxiliary pushdown automata

Abstract

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.