Characterizing the polynomial hierarchy by alternating auxiliary pushdown automata
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 23 (1989) no. 1, pp. 87-99.
@article{ITA_1989__23_1_87_0,
     author = {Jenner, Birgit and Kirsig, Bernd},
     title = {Characterizing the polynomial hierarchy by alternating auxiliary pushdown automata},
     journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications},
     pages = {87--99},
     publisher = {EDP-Sciences},
     volume = {23},
     number = {1},
     year = {1989},
     zbl = {0665.68038},
     mrnumber = {990069},
     language = {en},
     url = {http://www.numdam.org/item/ITA_1989__23_1_87_0/}
}
TY  - JOUR
AU  - Jenner, Birgit
AU  - Kirsig, Bernd
TI  - Characterizing the polynomial hierarchy by alternating auxiliary pushdown automata
JO  - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
PY  - 1989
DA  - 1989///
SP  - 87
EP  - 99
VL  - 23
IS  - 1
PB  - EDP-Sciences
UR  - http://www.numdam.org/item/ITA_1989__23_1_87_0/
UR  - https://zbmath.org/?q=an%3A0665.68038
UR  - https://www.ams.org/mathscinet-getitem?mr=990069
LA  - en
ID  - ITA_1989__23_1_87_0
ER  - 
Jenner, Birgit; Kirsig, Bernd. Characterizing the polynomial hierarchy by alternating auxiliary pushdown automata. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 23 (1989) no. 1, pp. 87-99. http://www.numdam.org/item/ITA_1989__23_1_87_0/

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. S. A. Cook, Characterizations of Pushdown Machines in Terms of Timebounded Computers, Journ. of the ACM 18,Vol. 1, 1971, pp. 4-18. | MR 292605 | Zbl 0222.02035

3. A. K. Chandra, D. C. Kozen, and L. J. Stockmeyer, Alternation, Journ. of the ACM 28, Vol. 1, 1981, pp. 114-133. | MR 603186 | Zbl 0473.68043

4. S. Greibach, Checking Automata and One-way Stack Languages, Journ. of Computer and System Sciences, Vol. 3, 1969, pp. 196-217. | MR 243953 | Zbl 0174.02702

5. J. E. Hopcroft, and J. D. Ullman, Introduction to Automata Theory, Languages, and Computation, Addison-Wesley, Reading, Mass., 1979. | MR 645539 | Zbl 0426.68001

6. N. Immerman, Nondeterministic Space is Closed Under Complement, Techn. Report, Yale University, YALEU/DCS/TR 552, July 1987. | MR 961049

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.

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. | MR 912734 | Zbl 0629.68051

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.

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. | MR 789889 | Zbl 0589.68058

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. | MR 935790

12. L. J. Stockmeyer, The Polynomial-time Hierarchy, Theoret. Comp. Sci.,Vol. 3, 1976, pp. 1-22. | MR 438810 | Zbl 0353.02024

13. I. H. Sudborough, On the Tape Complexity of Deterministic Context-Free Languages, Journ. of the ACM 25, Vol. 3, 1978, pp. 405-414. | MR 498563 | Zbl 0379.68054

14. R. Szelepcsényi, The Method of Forcing for Nondeterministic Automata, Bull. European Assoc. Theoret. Comp. Sci. No. 33, Oct. 1987 pp. 96-100. | Zbl 0664.68082