A hierarchy that does not collapse : alternations in low level space

Viliam Geffert

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

  • Volume: 28, Issue: 5, page 465-512
  • ISSN: 0988-3754

How to cite


Geffert, Viliam. "A hierarchy that does not collapse : alternations in low level space." RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications 28.5 (1994): 465-512. <http://eudml.org/doc/92491>.

author = {Geffert, Viliam},
journal = {RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications},
keywords = {alternation hierarchy},
language = {eng},
number = {5},
pages = {465-512},
publisher = {EDP-Sciences},
title = {A hierarchy that does not collapse : alternations in low level space},
url = {http://eudml.org/doc/92491},
volume = {28},
year = {1994},

AU - Geffert, Viliam
TI - A hierarchy that does not collapse : alternations in low level space
JO - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
PY - 1994
PB - EDP-Sciences
VL - 28
IS - 5
SP - 465
EP - 512
LA - eng
KW - alternation hierarchy
UR - http://eudml.org/doc/92491
ER -


  1. 1. L. BABAI and S. MORAN, Arthur-Merlin games: A randomized proof-system, and a hierarchy of complexity classes, J. Comput. Syst. Sciences, 1988, 36, pp. 254-276. Zbl0652.03029MR950433
  2. 2. T. BAKER, J. GILL and R. SOLOVAY, Relativizations of the P =?NP question, SIAM J. Comput., 1975, 4(4), pp. 431-442. Zbl0323.68033MR395311
  3. 3. B. von BRAUNMUHL, Alternation for two-way machines with sublogarithmic space, to appear in Proc. of STACS'93. Zbl0797.68056MR1249277
  4. 4. B. von BRAUNMUHL, R. GENGLER and R. RETTINGER, The alternation hierarchy for machines with sublogarithmic space is infinite, Research Report 8589-CS, University of Bonn, 1993. Zbl0796.68099MR1288535
  5. 5. A. K. CHANDRA, D. KOZEN and L. J. STOCKMEYER, Alternation, J. Assoc. Comput. Mach., 1981, 28, pp.114-133. Zbl0473.68043MR603186
  6. 6. 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
  7. 7. A. R. FREEDMAN and R. E. LADNER, Space bounds for processing contentless inputs, J. Comput. Syst. Sciences, 1975, 11, pp.118-128. Zbl0307.68036MR398161
  8. 8. V. GEFFERT, Nondeterministic computations in sublogarithmic space and space constructibility, SIAM J. Comput., 1991, 20(3), pp. 484-498. Zbl0762.68022MR1094527
  9. 9. V. GEFFERT, Sublogarithmic ∑2-SPACE is not closed under complement and other separation results, RAIRO Theoretical Informaties and Applications, 1993, 27(4), pp. 349-366. Zbl0804.68047MR1238056
  10. 10. V. GEFFERT, Tally versions of the Savitch and Immerman-Szelepcsényi theorems for sublogarithmic space, SIAM J. Comput., 1993, 22(1), pp.102-113. Zbl0766.68039MR1202863
  11. 11. J. HARTMANIS, The collapsing hierarchies, EATCS Bulletin, 1987, 33, pp. 26-39. Zbl0661.68047
  12. 12. L. A. HEMACHANDRA, The strong exponential hierarchy collapses, Proc. of 19th ACM STOC Conference, 1987, pp.110-122. 
  13. 13. N. IMMERMAN, Nondeterministic space is closed under complement, SIAM J. Comput., 1988, 17, pp. 935-938. Zbl0668.68056MR961049
  14. 14. K. IWAMA, ASPACE( o (log log)) is regular, SIAM J. Comput., 1983, 22(1), pp. 136-146. Zbl0767.68039MR1202865
  15. 15. 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
  16. 16. M. LIŚKIEWICZ and R. REISCHUK, Separating the lower levels of the sublogarithmic space hierarchy, to appear in Proc. of STACS'93. Zbl0799.68092MR1249278
  17. 17. M. LIŚKIEWICZ and R. REISCHUK, The sublogarithmic space hierarchy is infinite, Technical Report, Technical University of Darmstadt, 1993. Zbl0799.68092
  18. 18. 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
  19. 19. U. SCHÖNING and K. WAGNER, Collapsing oracle hiérarchies, census fonctions, and logarithmically many queries, Proc. of STACS'88, Springer-Verlag, LNCS, 294, 1988, pp. 91-97. Zbl0648.68065MR935790
  20. 20. J. SEIFERAS, A note on notions of tape constructibility, Technical Report CSD-TR-187, Pennsylvania State University, 1976. 
  21. 21. R. E. STEARNS, J. HARTMANIS and P. M. LEWIS II, Hierarchies of memory limited computations, Proc. of 1965 IEEE Conference Record on Switching Circuit Theory and Logical Design, 1965, pp. 179-190. Zbl0229.02033
  22. 22. R. SZELEPCSÉNYI, The method of forced enumeration for nondeterministic automata, Acta Informatica, 1988, 26, pp. 279-284. Zbl0638.68046MR975334
  23. 23. 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
  24. 24. S. TODA, ∑2-SPACE (n) is closed under complement J. Comput Syst. Sciences, 1987, 35, pp. 145-152. Zbl0654.68053MR910209
  25. 25. A. YAO, Separating the polynomial time hierarchy by oracles, Proc. of 26th FOCS, 1985, pp. 1-10. 

NotesEmbed ?


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.