Characterizing the polynomial hierarchy by alternating auxiliary pushdown automata
Jenner, Birgit ; Kirsig, Bernd
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 23 (1989), p. 87-99 / Harvested from Numdam
Access to full text
Full (PDF)
Full (DJVU)
Publié le : 1989-01-01
@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},
     volume = {23},
     year = {1989},
     pages = {87-99},
     mrnumber = {990069},
     zbl = {0665.68038},
     language = {en},
     url = {http://dml.mathdoc.fr/item/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) pp. 87-99. http://gdmltest.u-ga.fr/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