A hierarchy that does not collapse : alternations in low level space
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 28 (1994) no. 5, pp. 465-512. 
@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},
     pages = {465--512},
     publisher = {EDP-Sciences},
     volume = {28},
     number = {5},
     year = {1994},
     mrnumber = {1296648},
     zbl = {0884.68054},
     language = {en},
     url = {http://archive.numdam.org/item/ITA_1994__28_5_465_0/}
}
TY  - JOUR
AU  - Geffert, Viliam
TI  - A hierarchy that does not collapse : alternations in low level space
JO  - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
PY  - 1994
SP  - 465
EP  - 512
VL  - 28
IS  - 5
PB  - EDP-Sciences
UR  - http://archive.numdam.org/item/ITA_1994__28_5_465_0/
LA  - en
ID  - ITA_1994__28_5_465_0
ER  - 
%0 Journal Article
%A Geffert, Viliam
%T A hierarchy that does not collapse : alternations in low level space
%J RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
%D 1994
%P 465-512
%V 28
%N 5
%I EDP-Sciences
%U http://archive.numdam.org/item/ITA_1994__28_5_465_0/
%G en
%F 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) no. 5, pp. 465-512. http://archive.numdam.org/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 | Zbl

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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