Sublogarithmic -space is not closed under complement and other separation results
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications (1993)
- Volume: 27, Issue: 4, page 349-366
- ISSN: 0988-3754
Access Full Article
topHow to cite
topGeffert, V.. "Sublogarithmic $\sum _2$-space is not closed under complement and other separation results." RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications 27.4 (1993): 349-366. <http://eudml.org/doc/92456>.
@article{Geffert1993,
author = {Geffert, V.},
journal = {RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications},
keywords = {space complexity; complexity classes; alternating Turing machine},
language = {eng},
number = {4},
pages = {349-366},
publisher = {EDP-Sciences},
title = {Sublogarithmic $\sum _2$-space is not closed under complement and other separation results},
url = {http://eudml.org/doc/92456},
volume = {27},
year = {1993},
}
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
PB - EDP-Sciences
VL - 27
IS - 4
SP - 349
EP - 366
LA - eng
KW - space complexity; complexity classes; alternating Turing machine
UR - http://eudml.org/doc/92456
ER -
References
top- 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. Zbl0900.68265MR1127167
- 2. A. K. CHANDRA, D. KOZEN, L. J. STOCKMEYER, Alternation, J. Assoc. Comput. Mach., 1981, 28, pp. 114-133. Zbl0473.68043MR603186
- 3. A. K. CHANDRA and L. J. STOCKMEYER, Alternation, Proc. of 17th I.E.E.E.-F.O.C.S., 1976, pp. 98-108. MR520888
- 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). Zbl0635.68040MR896396
- 5. A. R. FREEDMAN and R. E. LADNER, Space bounds for processing counterless inputs, J. Comput. Syst. Sciences, 1975, 11, pp. 118-128. Zbl0307.68036MR398161
- 6. V. GEFFERT, Nondeterministic computations in sublogarithmic space and space constructibility, S.I.A.M. J. Comput., 1991, 20, No. 3, pp. 484-498. Zbl0762.68022MR1094527
- 7. N. IMMERMAN, Nondeterministic space is closed under complement, S.I.A.M. J. Comput., 1988, 17, pp. 935-938. Zbl0668.68056MR961049
- 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. Zbl0668.68055MR984485
- 9. D. KOZEN, On parallelism in Turing machines, 17th I.E.E.E.-F.O.C.S., 1976, pp. 89-97. MR464696
- 10. D. RANJAN, R. CHANG, and J. HARTMANIS, Space bounded computations: Review and new separation results, Theoret. Comp. Sci., 1991, 80, pp. 289-302. Zbl0745.68051MR1117067
- 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. Zbl0648.68065MR935790
- 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. Zbl0423.68011MR559693
- 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. Zbl0229.02033
- 15. R. SZELEPCSÉNYI, The method of forced enumeration for nondeterministic automata, Acta Informatica, 1988, 26, pp. 279-284. Zbl0638.68046MR975334
- 16. A. SZEPIETOWSKI, Some remarks on the alternating hierarchy and closure under complement for sublogarithmic space, Information Processing Letters, 1989, 33, pp. 73-78. Zbl0684.68062MR1031596
- 17. S. TODA, ∑2-SPACE(n) is closed under complement, J. Comput. Syst. Sciences, 1987, 35, pp. 145-152. Zbl0654.68053MR910209
Citations in EuDML Documents
topNotesEmbed ?
topTo embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.