Free Access
Issue
RAIRO-Theor. Inf. Appl.
Volume 28, Number 5, 1994
Page(s) 465 - 512
DOI https://doi.org/10.1051/ita/1994280504651
Published online 01 February 2017
  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. [MR: 950433] [Zbl: 0652.03029]
  2. 2. T. BAKER, J. GILL and R. SOLOVAY, Relativizations of the P =?NP question, SIAM J. Comput., 1975, 4(4), pp. 431-442. [MR: 395311] [Zbl: 0323.68033]
  3. 3. B. von BRAUNMUHL, Alternation for two-way machines with sublogarithmic space, to appear in Proc. of STACS'93. [MR: 1249277] [Zbl: 0797.68056]
  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. [Zbl: 0796.68099] [MR: 1288535]
  5. 5. A. K. CHANDRA, D. KOZEN and L. J. STOCKMEYER, Alternation, J. Assoc. Comput. Mach., 1981, 28, pp.114-133. [MR: 603186] [Zbl: 0473.68043]
  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). [MR: 896396] [Zbl: 0635.68040]
  7. 7. A. R. FREEDMAN and R. E. LADNER, Space bounds for processing contentless inputs, J. Comput. Syst. Sciences, 1975, 11, pp.118-128. [MR: 398161] [Zbl: 0307.68036]
  8. 8. V. GEFFERT, Nondeterministic computations in sublogarithmic space and space constructibility, SIAM J. Comput., 1991, 20(3), pp. 484-498. [MR: 1094527] [Zbl: 0762.68022]
  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. [EuDML: 92456] [MR: 1238056] [Zbl: 0804.68047]
  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. [MR: 1202863] [Zbl: 0766.68039]
  11. 11. J. HARTMANIS, The collapsing hierarchies, EATCS Bulletin, 1987, 33, pp. 26-39. [Zbl: 0661.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. [MR: 961049] [Zbl: 0668.68056]
  14. 14. K. IWAMA, ASPACE( o (log log)) is regular, SIAM J. Comput., 1983, 22(1), pp. 136-146. [MR: 1202865] [Zbl: 0767.68039]
  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. [MR: 984485] [Zbl: 0668.68055]
  16. 16. M. LIŚKIEWICZ and R. REISCHUK, Separating the lower levels of the sublogarithmic space hierarchy, to appear in Proc. of STACS'93. [MR: 1249278] [Zbl: 0799.68092]
  17. 17. M. LIŚKIEWICZ and R. REISCHUK, The sublogarithmic space hierarchy is infinite, Technical Report, Technical University of Darmstadt, 1993. [Zbl: 0799.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. [MR: 1117067] [Zbl: 0745.68051]
  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. [MR: 935790] [Zbl: 0648.68065]
  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. [Zbl: 0229.02033]
  22. 22. R. SZELEPCSÉNYI, The method of forced enumeration for nondeterministic automata, Acta Informatica, 1988, 26, pp. 279-284. [MR: 975334] [Zbl: 0638.68046]
  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. [MR: 1031596] [Zbl: 0684.68062]
  24. 24. S. TODA, ∑2-SPACE (n) is closed under complement J. Comput Syst. Sciences, 1987, 35, pp. 145-152. [MR: 910209] [Zbl: 0654.68053]
  25. 25. A. YAO, Separating the polynomial time hierarchy by oracles, Proc. of 26th FOCS, 1985, pp. 1-10.

Current usage metrics show cumulative count of Article Views (full-text article views including HTML views, PDF and ePub downloads, according to the available data) and Abstracts Views on Vision4Press platform.

Data correspond to usage on the plateform after 2015. The current usage metrics is available 48-96 hours after online publication and is updated daily on week days.

Initial download of the metrics may take a while.