Sublogarithmic ∑ 2 -space is not closed under complement and other separation results
Geffert, V.
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Volume 27 (1993), p. 349-366 / Harvested from Numdam
Access to full text
Full (PDF)
Full (DJVU)
Published online : 1993-01-01
@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},
     volume = {27},
     year = {1993},
     pages = {349-366},
     mrnumber = {1238056},
     zbl = {0804.68047},
     language = {en},
     url = {http://dml.mathdoc.fr/item/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, Volume 27 (1993) pp. 349-366. http://gdmltest.u-ga.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. | MR 1127167 | Zbl 0900.68265

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

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 520888

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

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

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

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

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

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

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

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

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

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 0229.02033

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

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

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