EDP Sciences logo
Subscriber Authentication Point
Search
Menu
All issues Volume 28 / No 5 (1994) RAIRO-Theor. Inf. Appl., 28 5 (1994) 465-512 References
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] [Google Scholar]
  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] [Google Scholar]
  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] [Google Scholar]
  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] [Google Scholar]
  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] [Google Scholar]
  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] [Google Scholar]
  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] [Google Scholar]
  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] [Google Scholar]
  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] [Google Scholar]
  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] [Google Scholar]
  11. 11. J. HARTMANIS, The collapsing hierarchies, EATCS Bulletin, 1987, 33, pp. 26-39. [Zbl: 0661.68047] [Google Scholar]
  12. 12. L. A. HEMACHANDRA, The strong exponential hierarchy collapses, Proc. of 19th ACM STOC Conference, 1987, pp.110-122. [Google Scholar]
  13. 13. N. IMMERMAN, Nondeterministic space is closed under complement, SIAM J. Comput., 1988, 17, pp. 935-938. [MR: 961049] [Zbl: 0668.68056] [Google Scholar]
  14. 14. K. IWAMA, ASPACE( o (log log)) is regular, SIAM J. Comput., 1983, 22(1), pp. 136-146. [MR: 1202865] [Zbl: 0767.68039] [Google Scholar]
  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] [Google Scholar]
  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] [Google Scholar]
  17. 17. M. LIŚKIEWICZ and R. REISCHUK, The sublogarithmic space hierarchy is infinite, Technical Report, Technical University of Darmstadt, 1993. [Zbl: 0799.68092] [Google Scholar]
  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] [Google Scholar]
  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] [Google Scholar]
  20. 20. J. SEIFERAS, A note on notions of tape constructibility, Technical Report CSD-TR-187, Pennsylvania State University, 1976. [Google Scholar]
  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] [Google Scholar]
  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] [Google Scholar]
  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] [Google Scholar]
  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] [Google Scholar]
  25. 25. A. YAO, Separating the polynomial time hierarchy by oracles, Proc. of 26th FOCS, 1985, pp. 1-10. [Google Scholar]

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.