@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://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 SP - 87 EP - 99 VL - 23 IS - 1 PB - EDP-Sciences UR - http://www.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://www.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, Tome 23 (1989) no. 1, pp. 87-99. http://www.numdam.org/item/ITA_1989__23_1_87_0/
1. Two Applications of Complementation via Inductive Counting, manuscript, Sept. 1987.
, , , , and ,2. Characterizations of Pushdown Machines in Terms of Timebounded Computers, Journ. of the ACM 18,Vol. 1, 1971, pp. 4-18. | MR | Zbl
,3. Alternation, Journ. of the ACM 28, Vol. 1, 1981, pp. 114-133. | MR | Zbl
, , and ,4. Checking Automata and One-way Stack Languages, Journ. of Computer and System Sciences, Vol. 3, 1969, pp. 196-217. | MR | Zbl
,5. Introduction to Automata Theory, Languages, and Computation, Addison-Wesley, Reading, Mass., 1979. | MR | Zbl
, and ,6. Nondeterministic Space is Closed Under Complement, Techn. Report, Yale University, YALEU/DCS/TR 552, July 1987. | MR
,7. The Logarithmic Alternation Hierarchy Collapses: A∑L2 = A∏L2 (extended version), to be published in Information and Computation.
, , and ,8. 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
, , and ,9. Alternating Pushdown Automata, Proc. of the 19th IEEE Symp. on Foundations of Comp. Sci., Ann Arbor, Mich., 1978, pp. 92-106.
, , and ,10. Alternation Bounded Auxiliary Push-down Automata, Information and Control, Vol. 62, 1984, pp. 93-108. | MR | Zbl
, , and ,11. Collapsing Oracle Hierarchies, Census Functions and Logarithmically Many Queries, Report No. 140,Universität Augsburg, May 1987. | MR
, and ,12. The Polynomial-time Hierarchy, Theoret. Comp. Sci.,Vol. 3, 1976, pp. 1-22. | MR | Zbl
,13. On the Tape Complexity of Deterministic Context-Free Languages, Journ. of the ACM 25, Vol. 3, 1978, pp. 405-414. | MR | Zbl
,14. The Method of Forcing for Nondeterministic Automata, Bull. European Assoc. Theoret. Comp. Sci. No. 33, Oct. 1987 pp. 96-100. | Zbl
,