Sublogarithmic ∑ 2 -space is not closed under complement and other separation results

V. Geffert

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications (1993)

  • Volume: 27, Issue: 4, page 349-366
  • ISSN: 0988-3754

How to cite

top

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 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. 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. 2. A. K. CHANDRA, D. KOZEN, L. J. STOCKMEYER, Alternation, J. Assoc. Comput. Mach., 1981, 28, pp. 114-133. Zbl0473.68043MR603186
  3. 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. 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. 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. 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. 7. N. IMMERMAN, Nondeterministic space is closed under complement, S.I.A.M. J. Comput., 1988, 17, pp. 935-938. Zbl0668.68056MR961049
  8. 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. 9. D. KOZEN, On parallelism in Turing machines, 17th I.E.E.E.-F.O.C.S., 1976, pp. 89-97. MR464696
  10. 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. 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. 12. J. SEIFERAS, A note on notions of tape constructibility, Technical Report CSD-TR-187, Pennsylvania State University, 1976. 
  13. 13. M. SIPSER, Halting space bounded computations, Theoret. Comp. Sci., 1980, 10, pp. 335-338. Zbl0423.68011MR559693
  14. 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. 15. R. SZELEPCSÉNYI, The method of forced enumeration for nondeterministic automata, Acta Informatica, 1988, 26, pp. 279-284. Zbl0638.68046MR975334
  16. 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. 17. S. TODA, ∑2-SPACE(n) is closed under complement, J. Comput. Syst. Sciences, 1987, 35, pp. 145-152. Zbl0654.68053MR910209

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.