Characterizing the polynomial hierarchy by alternating auxiliary pushdown automata
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, STACS 88, 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},
     mrnumber = {990069},
     zbl = {0665.68038},
     language = {en},
     url = {http://archive.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
SP  - 87
EP  - 99
VL  - 23
IS  - 1
PB  - EDP-Sciences
UR  - http://archive.numdam.org/item/ITA_1989__23_1_87_0/
LA  - en
ID  - ITA_1989__23_1_87_0
ER  - 
%0 Journal Article
%A Jenner, Birgit
%A Kirsig, Bernd
%T Characterizing the polynomial hierarchy by alternating auxiliary pushdown automata
%J RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
%D 1989
%P 87-99
%V 23
%N 1
%I EDP-Sciences
%U http://archive.numdam.org/item/ITA_1989__23_1_87_0/
%G en
%F ITA_1989__23_1_87_0
Jenner, Birgit; Kirsig, Bernd. Characterizing the polynomial hierarchy by alternating auxiliary pushdown automata. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, STACS 88, Tome 23 (1989) no. 1, pp. 87-99. http://archive.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 | Zbl

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

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

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

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

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 | Zbl

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 | Zbl

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

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

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 | Zbl

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