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

Voir la notice de l'article provenant de la source Numdam

@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://geodesic.mathdoc.fr/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://geodesic.mathdoc.fr/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://geodesic.mathdoc.fr/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://geodesic.mathdoc.fr/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. | Zbl | MR

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

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

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

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

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

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

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

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

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

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

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

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