Characterizing the polynomial hierarchy by alternating auxiliary pushdown automata

 Access to full text

 Full (PDF)

1. 1. A. BORODIN, S. A. COOK, P. W. DYMOND, W. L. RUZZO, and M. TOMPA, Two Applications of Complementation via Inductive Counting, manuscript, Sept. 1987. 
2. 2. S. A. COOK, Characterizations of Pushdown Machines in Terms of Timebounded Computers, Journ. of the ACM 18,Vol. 1, 1971, pp. 4-18. Zbl0222.02035MR292605
3. 3. A. K. CHANDRA, D. C. KOZEN, and L. J. STOCKMEYER, Alternation, Journ. of the ACM 28, Vol. 1, 1981, pp. 114-133. Zbl0473.68043MR603186
4. 4. S. GREIBACH, Checking Automata and One-way Stack Languages, Journ. of Computer and System Sciences, Vol. 3, 1969, pp. 196-217. Zbl0174.02702MR243953
5. 5. J. E. HOPCROFT, and J. D. ULLMAN, Introduction to Automata Theory, Languages, and Computation, Addison-Wesley, Reading, Mass., 1979. Zbl0426.68001MR645539
6. 6. N. IMMERMAN, Nondeterministic Space is Closed Under Complement, Techn. Report, Yale University, YALEU/DCS/TR 552, July 1987. Zbl0668.68056MR961049
7. 7. B. JENNER, B. KIRSIG, and K.-J. LANGE, The Logarithmic Alternation Hierarchy Collapses: A∑L2 = A∏L2 (extended version), to be published in Information and Computation. Zbl0629.68051
8. 8. K.-J. LANGE, B. JENNER, and B. KIRSIG, The Logarithmic Alternation Hierarchy Collapses: A∑L2 = A∏L2, Proc. of the 14th ICALP, Karlsruhe, July 1987, Lect. Notes in Comp. Sci., Vol. 267, pp.531-541. Zbl0629.68051MR912734
9. 9. R. E. LADNER, R. J. LIPTON, and L. J . STOCKMEYER, Alternating Pushdown Automata, Proc. of the 19th IEEE Symp. on Foundations of Comp. Sci., Ann Arbor, Mich., 1978, pp. 92-106. Zbl0538.68039
10. 10. R. E. LADNER, L. J. STOCKMEYER, and R. J. LIPTON, Alternation Bounded Auxiliary Push-down Automata, Information and Control, Vol. 62, 1984, pp. 93-108. Zbl0589.68058MR789889
11. 11. U. SCHÖNING, and K. W. WAGNER, Collapsing Oracle Hierarchies, Census Functions and Logarithmically Many Queries, Report No. 140,Universität Augsburg, May 1987. Zbl0648.68065MR935790
12. 12. L. J. STOCKMEYER, The Polynomial-time Hierarchy, Theoret. Comp. Sci.,Vol. 3, 1976, pp. 1-22. Zbl0353.02024MR438810
13. 13. I. H. SUDBOROUGH, On the Tape Complexity of Deterministic Context-Free Languages, Journ. of the ACM 25, Vol. 3, 1978, pp. 405-414. Zbl0379.68054MR498563
14. 14. R. SZELEPCSÉNYI, The Method of Forcing for Nondeterministic Automata, Bull. European Assoc. Theoret. Comp. Sci. No. 33, Oct. 1987 pp. 96-100. Zbl0664.68082