Evaluation of polynomials with super-preconditioning
Richard J. Lipton, Larry J. Stockmeyer
STOC 1976
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.
Richard J. Lipton, Larry J. Stockmeyer
STOC 1976
Ashok K. Chandra, Dexter C. Kozen, et al.
Journal of the ACM
Richard J. Lipton
FOCS 1975
Ronald Fagin, Larry J. Stockmeyer, et al.
Information and Computation