A hierarchy that does not collapse : alternations in low level space

 Access to full text

 Full (PDF)

1. 1. L. BABAI and S. MORAN, Arthur-Merlin games: A randomized proof-system, and a hierarchy of complexity classes, J. Comput. Syst. Sciences, 1988, 36, pp. 254-276. Zbl0652.03029MR950433
2. 2. T. BAKER, J. GILL and R. SOLOVAY, Relativizations of the P =?NP question, SIAM J. Comput., 1975, 4(4), pp. 431-442. Zbl0323.68033MR395311
3. 3. B. von BRAUNMUHL, Alternation for two-way machines with sublogarithmic space, to appear in Proc. of STACS'93. Zbl0797.68056MR1249277
4. 4. B. von BRAUNMUHL, R. GENGLER and R. RETTINGER, The alternation hierarchy for machines with sublogarithmic space is infinite, Research Report 8589-CS, University of Bonn, 1993. Zbl0796.68099MR1288535
5. 5. A. K. CHANDRA, D. KOZEN and L. J. STOCKMEYER, Alternation, J. Assoc. Comput. Mach., 1981, 28, pp.114-133. Zbl0473.68043MR603186
6. 6. J. H. CHANG, O. H. IBARRA, B. RAVIKUMAR and L. BERMAN, Some observations concerning alternating Turing machines using small space, Inform. Process. Lett., 1987, 25, pp.1-9 (Erratum: 27, 1988, 53). Zbl0635.68040MR896396
7. 7. A. R. FREEDMAN and R. E. LADNER, Space bounds for processing contentless inputs, J. Comput. Syst. Sciences, 1975, 11, pp.118-128. Zbl0307.68036MR398161
8. 8. V. GEFFERT, Nondeterministic computations in sublogarithmic space and space constructibility, SIAM J. Comput., 1991, 20(3), pp. 484-498. Zbl0762.68022MR1094527
9. 9. V. GEFFERT, Sublogarithmic ∑2-SPACE is not closed under complement and other separation results, RAIRO Theoretical Informaties and Applications, 1993, 27(4), pp. 349-366. Zbl0804.68047MR1238056
10. 10. V. GEFFERT, Tally versions of the Savitch and Immerman-Szelepcsényi theorems for sublogarithmic space, SIAM J. Comput., 1993, 22(1), pp.102-113. Zbl0766.68039MR1202863
11. 11. J. HARTMANIS, The collapsing hierarchies, EATCS Bulletin, 1987, 33, pp. 26-39. Zbl0661.68047
12. 12. L. A. HEMACHANDRA, The strong exponential hierarchy collapses, Proc. of 19th ACM STOC Conference, 1987, pp.110-122. 
13. 13. N. IMMERMAN, Nondeterministic space is closed under complement, SIAM J. Comput., 1988, 17, pp. 935-938. Zbl0668.68056MR961049
14. 14. K. IWAMA, ASPACE( o (log log)) is regular, SIAM J. Comput., 1983, 22(1), pp. 136-146. Zbl0767.68039MR1202865
15. 15. B. JENNER, B. KIRSIG and K. LANGE, The logarithmic alternation hierarchy collapses: A∑L2 = AπL2, Information and Computation, 1989, 80, pp. 269-288. Zbl0668.68055MR984485
16. 16. M. LIŚKIEWICZ and R. REISCHUK, Separating the lower levels of the sublogarithmic space hierarchy, to appear in Proc. of STACS'93. Zbl0799.68092MR1249278
17. 17. M. LIŚKIEWICZ and R. REISCHUK, The sublogarithmic space hierarchy is infinite, Technical Report, Technical University of Darmstadt, 1993. Zbl0799.68092
18. 18. D. RANJAN, R. CHANG and J. HARTMANIS, Space bounded computations: Review and new separation results, Theoret. Comp. Sci., 1991, 80, pp. 289-302. Zbl0745.68051MR1117067
19. 19. U. SCHÖNING and K. WAGNER, Collapsing oracle hiérarchies, census fonctions, and logarithmically many queries, Proc. of STACS'88, Springer-Verlag, LNCS, 294, 1988, pp. 91-97. Zbl0648.68065MR935790
20. 20. J. SEIFERAS, A note on notions of tape constructibility, Technical Report CSD-TR-187, Pennsylvania State University, 1976. 
21. 21. R. E. STEARNS, J. HARTMANIS and P. M. LEWIS II, Hierarchies of memory limited computations, Proc. of 1965 IEEE Conference Record on Switching Circuit Theory and Logical Design, 1965, pp. 179-190. Zbl0229.02033
22. 22. R. SZELEPCSÉNYI, The method of forced enumeration for nondeterministic automata, Acta Informatica, 1988, 26, pp. 279-284. Zbl0638.68046MR975334
23. 23. A. SZEPIETOWSKI, Some remarks on the alternating hierarchy and closure under complement for sublogarithmic space, Information Processing Letters, 1989, 33, pp. 73-78. Zbl0684.68062MR1031596
24. 24. S. TODA, ∑2-SPACE (n) is closed under complement J. Comput Syst. Sciences, 1987, 35, pp. 145-152. Zbl0654.68053MR910209
25. 25. A. YAO, Separating the polynomial time hierarchy by oracles, Proc. of 26th FOCS, 1985, pp. 1-10. 

1. Viliam Geffert, Norbert Popély, A space lower bound for acceptance by one-way ${\Pi }_2$-alternating machines
2. Viliam Geffert, Norbert Popély, A Space Lower Bound for Acceptance by One-Way Π-Alternating Machines