Sublogarithmic ∑ 2 -space is not closed under complement and other separation results
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 27 (1993) no. 4, pp. 349-366. 
@article{ITA_1993__27_4_349_0,
     author = {Geffert, V.},
     title = {Sublogarithmic $\sum _2$-space is not closed under complement and other separation results},
     journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications},
     pages = {349--366},
     publisher = {EDP-Sciences},
     volume = {27},
     number = {4},
     year = {1993},
     mrnumber = {1238056},
     zbl = {0804.68047},
     language = {en},
     url = {http://archive.numdam.org/item/ITA_1993__27_4_349_0/}
}
TY  - JOUR
AU  - Geffert, V.
TI  - Sublogarithmic $\sum _2$-space is not closed under complement and other separation results
JO  - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
PY  - 1993
SP  - 349
EP  - 366
VL  - 27
IS  - 4
PB  - EDP-Sciences
UR  - http://archive.numdam.org/item/ITA_1993__27_4_349_0/
LA  - en
ID  - ITA_1993__27_4_349_0
ER  - 
%0 Journal Article
%A Geffert, V.
%T Sublogarithmic $\sum _2$-space is not closed under complement and other separation results
%J RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
%D 1993
%P 349-366
%V 27
%N 4
%I EDP-Sciences
%U http://archive.numdam.org/item/ITA_1993__27_4_349_0/
%G en
%F ITA_1993__27_4_349_0
Geffert, V. Sublogarithmic $\sum _2$-space is not closed under complement and other separation results. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 27 (1993) no. 4, pp. 349-366. http://archive.numdam.org/item/ITA_1993__27_4_349_0/

1. P. Van Emde Boas, Machine models and simulations, I.T.L.I. Prepublication Series for Computation and Complexity Theory, CT-89-02, to appear in: J. van Leeuwen (ed): Handbook of Theoretical Computer Science, North-Holland. | MR | Zbl

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

3. A. K. Chandra and L. J. Stockmeyer, Alternation, Proc. of 17th I.E.E.E.-F.O.C.S., 1976, pp. 98-108. | MR

4. 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

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

6. V. Geffert, Nondeterministic computations in sublogarithmic space and space constructibility, S.I.A.M. J. Comput., 1991, 20, No. 3, pp. 484-498. | MR | Zbl

7. N. Immerman, Nondeterministic space is closed under complement, S.I.A.M. J. Comput., 1988, 17, pp. 935-938. | MR | Zbl

8. 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

9. D. Kozen, On parallelism in Turing machines, 17th I.E.E.E.-F.O.C.S., 1976, pp. 89-97. | MR

10. 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

11. U. Schoning and K. Wagner, Collapsing oracle hierarchies, census functions, and logarithmically many queries, Proc. of STACS'88, Springer-Verlag, LNCS 294, 1988, pp. 91-97. | MR | Zbl

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

13. M. Sipser, Halting space bounded computations, Theoret. Comp. Sci., 1980, 10, pp. 335-338. | MR | Zbl

14. R. E. Stearns, J. Hartmanis, and P. M. Lewis Ii, Hierarchies of memory limited computations, In 1965 I.E.E.E. Conference Record on Switching Circuit Theory and Logical Design, 1965, pp. 179-190. | Zbl

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

16. 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

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