A hierarchy that does not collapse : alternations in low level space
Geffert, Viliam
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 28 (1994), p. 465-512 / Harvested from Numdam
Access to full text
Full (PDF)
Full (DJVU) 
@article{ITA_1994__28_5_465_0,
     author = {Geffert, Viliam},
     title = {A hierarchy that does not collapse : alternations in low level space},
     journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications},
     volume = {28},
     year = {1994},
     pages = {465-512},
     mrnumber = {1296648},
     zbl = {0884.68054},
     language = {en},
     url = {http://dml.mathdoc.fr/item/ITA_1994__28_5_465_0}
}

Geffert, Viliam. A hierarchy that does not collapse : alternations in low level space. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 28 (1994) pp. 465-512. http://gdmltest.u-ga.fr/item/ITA_1994__28_5_465_0/

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. | MR 950433 | Zbl 0652.03029

2. T. Baker, J. Gill and R. Solovay, Relativizations of the P =?NP question, SIAM J. Comput., 1975, 4(4), pp. 431-442. | MR 395311 | Zbl 0323.68033

3. B. Von Braunmuhl, Alternation for two-way machines with sublogarithmic space, to appear in Proc. of STACS'93. | MR 1249277 | Zbl 0797.68056

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. | MR 1288535

5. A. K. Chandra, D. Kozen and L. J. Stockmeyer, Alternation, J. Assoc. Comput. Mach., 1981, 28, pp.114-133. | MR 603186 | Zbl 0473.68043

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). | MR 896396 | Zbl 0635.68040

7. A. R. Freedman and R. E. Ladner, Space bounds for processing contentless inputs, J. Comput. Syst. Sciences, 1975, 11, pp.118-128. | MR 398161 | Zbl 0307.68036

8. V. Geffert, Nondeterministic computations in sublogarithmic space and space constructibility, SIAM J. Comput., 1991, 20(3), pp. 484-498. | MR 1094527 | Zbl 0762.68022

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. | Numdam | MR 1238056 | Zbl 0804.68047

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. | MR 1202863 | Zbl 0766.68039

11. J. Hartmanis, The collapsing hierarchies, EATCS Bulletin, 1987, 33, pp. 26-39. | Zbl 0661.68047

12. L. A. Hemachandra, The strong exponential hierarchy collapses, Proc. of 19th ACM STOC Conference, 1987, pp.110-122.

13. N. Immerman, Nondeterministic space is closed under complement, SIAM J. Comput., 1988, 17, pp. 935-938. | MR 961049 | Zbl 0668.68056

14. K. Iwama, ASPACE( o (log log)) is regular, SIAM J. Comput., 1983, 22(1), pp. 136-146. | MR 1202865 | Zbl 0767.68039

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. | MR 984485 | Zbl 0668.68055

16. M. Liśkiewicz and R. Reischuk, Separating the lower levels of the sublogarithmic space hierarchy, to appear in Proc. of STACS'93. | MR 1249278 | Zbl 0799.68092

17. M. Liśkiewicz and R. Reischuk, The sublogarithmic space hierarchy is infinite, Technical Report, Technical University of Darmstadt, 1993.

18. D. Ranjan, R. Chang and J. Hartmanis, Space bounded computations: Review and new separation results, Theoret. Comp. Sci., 1991, 80, pp. 289-302. | MR 1117067 | Zbl 0745.68051

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. | MR 935790 | Zbl 0648.68065

20. J. Seiferas, A note on notions of tape constructibility, Technical Report CSD-TR-187, Pennsylvania State University, 1976.

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. | Zbl 0229.02033

22. R. Szelepcsényi, The method of forced enumeration for nondeterministic automata, Acta Informatica, 1988, 26, pp. 279-284. | MR 975334 | Zbl 0638.68046

23. A. Szepietowski, Some remarks on the alternating hierarchy and closure under complement for sublogarithmic space, Information Processing Letters, 1989, 33, pp. 73-78. | MR 1031596 | Zbl 0684.68062

24. S. Toda, ∑2-SPACE (n) is closed under complement J. Comput Syst. Sciences, 1987, 35, pp. 145-152. | MR 910209 | Zbl 0654.68053

25. A. Yao, Separating the polynomial time hierarchy by oracles, Proc. of 26th FOCS, 1985, pp. 1-10.