@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://www.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://www.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://www.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, Volume 27 (1993) no. 4, pp. 349-366. http://www.numdam.org/item/ITA_1993__27_4_349_0/
1. 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. Alternation, J. Assoc. Comput. Mach., 1981, 28, pp. 114-133. | MR | Zbl
, , ,3. Alternation, Proc. of 17th I.E.E.E.-F.O.C.S., 1976, pp. 98-108. | MR
and ,4. Some observations concerning alternating Turing machines using small space, Inform. Process. Lett., 1987, 25, pp. 1-9 (Erratum: 27 (1988), 53). | MR | Zbl
, , , and ,5. Space bounds for processing counterless inputs, J. Comput. Syst. Sciences, 1975, 11, pp. 118-128. | MR | Zbl
and ,6. Nondeterministic computations in sublogarithmic space and space constructibility, S.I.A.M. J. Comput., 1991, 20, No. 3, pp. 484-498. | MR | Zbl
,7. Nondeterministic space is closed under complement, S.I.A.M. J. Comput., 1988, 17, pp. 935-938. | MR | Zbl
,8. The logarithmic alternation hierarchy collapses: A∑L2 = AπL2, Information and Computation, 1989, 80, pp. 269-288. | MR | Zbl
, , and ,9. On parallelism in Turing machines, 17th I.E.E.E.-F.O.C.S., 1976, pp. 89-97. | MR
,10. Space bounded computations: Review and new separation results, Theoret. Comp. Sci., 1991, 80, pp. 289-302. | MR | Zbl
, , and ,11. Collapsing oracle hierarchies, census functions, and logarithmically many queries, Proc. of STACS'88, Springer-Verlag, LNCS 294, 1988, pp. 91-97. | MR | Zbl
and ,12. A note on notions of tape constructibility, Technical Report CSD-TR-187, Pennsylvania State University, 1976.
,13. Halting space bounded computations, Theoret. Comp. Sci., 1980, 10, pp. 335-338. | MR | Zbl
,14. 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
, , and ,15. The method of forced enumeration for nondeterministic automata, Acta Informatica, 1988, 26, pp. 279-284. | MR | Zbl
,16. Some remarks on the alternating hierarchy and closure under complement for sublogarithmic space, Information Processing Letters, 1989, 33, pp. 73-78. | MR | Zbl
,17. ∑2-SPACE(n) is closed under complement, J. Comput. Syst. Sciences, 1987, 35, pp. 145-152. | MR | Zbl
,