×

Characterizing the polynomial hierarchy by alternating auxiliary pushdown automata. (English) Zbl 0665.68038

See the review of the preliminary version of this article [Lect. Notes Comput. Sci. 294, 118-125 (1988; Zbl 0644.68056)].

MSC:

68Q25 Analysis of algorithms and problem complexity
68Q45 Formal languages and automata
03D15 Complexity of computation (including implicit computational complexity)
PDFBibTeX XMLCite
Full Text: DOI EuDML

References:

[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.02035 MR292605 · Zbl 0222.02035 · doi:10.1145/321623.321625
[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.68043 MR603186 · Zbl 0473.68043 · doi:10.1145/322234.322243
[4] 4. S. GREIBACH, Checking Automata and One-way Stack Languages, Journ. of Computer and System Sciences, Vol. 3, 1969, pp. 196-217. Zbl0174.02702 MR243953 · Zbl 0174.02702 · doi:10.1016/S0022-0000(69)80012-7
[5] 5. J. E. HOPCROFT, and J. D. ULLMAN, Introduction to Automata Theory, Languages, and Computation, Addison-Wesley, Reading, Mass., 1979. Zbl0426.68001 MR645539 · Zbl 0426.68001
[6] 6. N. IMMERMAN, Nondeterministic Space is Closed Under Complement, Techn. Report, Yale University, YALEU/DCS/TR 552, July 1987. MR961049 · Zbl 0668.68056
[7] 7. B. JENNER, B. KIRSIG, and K.-J. LANGE, The Logarithmic Alternation Hierarchy Collapses: A\sum L2 = A\prod L2 (extended version), to be published in Information and Computation. · Zbl 0629.68051
[8] 8. K.-J. LANGE, B. JENNER, and B. KIRSIG, The Logarithmic Alternation Hierarchy Collapses: A\sum L2 = A\prod L2, Proc. of the 14th ICALP, Karlsruhe, July 1987, Lect. Notes in Comp. Sci., Vol. 267, pp.531-541. Zbl0629.68051 MR912734 · Zbl 0629.68051
[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. · Zbl 0538.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.68058 MR789889 · Zbl 0589.68058 · doi:10.1016/S0019-9958(84)80029-7
[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. MR935790 · Zbl 0648.68065
[12] 12. L. J. STOCKMEYER, The Polynomial-time Hierarchy, Theoret. Comp. Sci.,Vol. 3, 1976, pp. 1-22. Zbl0353.02024 MR438810 · Zbl 0353.02024 · doi:10.1016/0304-3975(76)90061-X
[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.68054 MR498563 · Zbl 0379.68054 · doi:10.1145/322077.322083
[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 · Zbl 0664.68082
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.