Characterizing the polynomial hierarchy by alternating auxiliary pushdown automata

Birgit Jenner; Bernd Kirsig

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications (1989)

  • Volume: 23, Issue: 1, page 87-99
  • ISSN: 0988-3754

How to cite

top

Jenner, Birgit, and Kirsig, Bernd. "Characterizing the polynomial hierarchy by alternating auxiliary pushdown automata." RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications 23.1 (1989): 87-99. <http://eudml.org/doc/92326>.

@article{Jenner1989,
author = {Jenner, Birgit, Kirsig, Bernd},
journal = {RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications},
keywords = {complexity theory; alternating auxiliary pushdown hierarchy; machine model; logarithmic alternation hierarchy; pushdown store; PSPACE; pushdown automata with unbounded alternation},
language = {eng},
number = {1},
pages = {87-99},
publisher = {EDP-Sciences},
title = {Characterizing the polynomial hierarchy by alternating auxiliary pushdown automata},
url = {http://eudml.org/doc/92326},
volume = {23},
year = {1989},
}

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
PB - EDP-Sciences
VL - 23
IS - 1
SP - 87
EP - 99
LA - eng
KW - complexity theory; alternating auxiliary pushdown hierarchy; machine model; logarithmic alternation hierarchy; pushdown store; PSPACE; pushdown automata with unbounded alternation
UR - http://eudml.org/doc/92326
ER -

References

top
  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

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.