@article{ITA_1994__28_5_465_0, author = {Geffert, Viliam}, title = {A hierarchy that does not collapse : alternations in low level space}, journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications}, pages = {465--512}, publisher = {EDP-Sciences}, volume = {28}, number = {5}, year = {1994}, mrnumber = {1296648}, zbl = {0884.68054}, language = {en}, url = {http://www.numdam.org/item/ITA_1994__28_5_465_0/} }
TY - JOUR 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 SP - 465 EP - 512 VL - 28 IS - 5 PB - EDP-Sciences UR - http://www.numdam.org/item/ITA_1994__28_5_465_0/ LA - en ID - ITA_1994__28_5_465_0 ER -
%0 Journal Article %A Geffert, Viliam %T A hierarchy that does not collapse : alternations in low level space %J RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications %D 1994 %P 465-512 %V 28 %N 5 %I EDP-Sciences %U http://www.numdam.org/item/ITA_1994__28_5_465_0/ %G en %F ITA_1994__28_5_465_0
Geffert, Viliam. A hierarchy that does not collapse : alternations in low level space. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Volume 28 (1994) no. 5, pp. 465-512. http://www.numdam.org/item/ITA_1994__28_5_465_0/
1. Arthur-Merlin games: A randomized proof-system, and a hierarchy of complexity classes, J. Comput. Syst. Sciences, 1988, 36, pp. 254-276. | MR | Zbl
and ,2. Relativizations of the P =?NP question, SIAM J. Comput., 1975, 4(4), pp. 431-442. | MR | Zbl
, and ,3. Alternation for two-way machines with sublogarithmic space, to appear in Proc. of STACS'93. | MR | Zbl
,4. The alternation hierarchy for machines with sublogarithmic space is infinite, Research Report 8589-CS, University of Bonn, 1993. | MR
, and ,5. Alternation, J. Assoc. Comput. Mach., 1981, 28, pp.114-133. | MR | Zbl
, and ,6. Some observations concerning alternating Turing machines using small space, Inform. Process. Lett., 1987, 25, pp.1-9 (Erratum: 27, 1988, 53). | MR | Zbl
, , and ,7. Space bounds for processing contentless inputs, J. Comput. Syst. Sciences, 1975, 11, pp.118-128. | MR | Zbl
and ,8. Nondeterministic computations in sublogarithmic space and space constructibility, SIAM J. Comput., 1991, 20(3), pp. 484-498. | MR | Zbl
,9. Sublogarithmic ∑2-SPACE is not closed under complement and other separation results, RAIRO Theoretical Informaties and Applications, 1993, 27(4), pp. 349-366. | Numdam | MR | Zbl
,10. Tally versions of the Savitch and Immerman-Szelepcsényi theorems for sublogarithmic space, SIAM J. Comput., 1993, 22(1), pp.102-113. | MR | Zbl
,11. The collapsing hierarchies, EATCS Bulletin, 1987, 33, pp. 26-39. | Zbl
,12. The strong exponential hierarchy collapses, Proc. of 19th ACM STOC Conference, 1987, pp.110-122.
,13. Nondeterministic space is closed under complement, SIAM J. Comput., 1988, 17, pp. 935-938. | MR | Zbl
,14. ASPACE( o (log log)) is regular, SIAM J. Comput., 1983, 22(1), pp. 136-146. | MR | Zbl
,15. The logarithmic alternation hierarchy collapses: A∑L2 = AπL2, Information and Computation, 1989, 80, pp. 269-288. | MR | Zbl
, and ,16. Separating the lower levels of the sublogarithmic space hierarchy, to appear in Proc. of STACS'93. | MR | Zbl
and ,17. The sublogarithmic space hierarchy is infinite, Technical Report, Technical University of Darmstadt, 1993.
and ,18. Space bounded computations: Review and new separation results, Theoret. Comp. Sci., 1991, 80, pp. 289-302. | MR | Zbl
, and ,19. Collapsing oracle hiérarchies, census fonctions, and logarithmically many queries, Proc. of STACS'88, Springer-Verlag, LNCS, 294, 1988, pp. 91-97. | MR | Zbl
and ,20. A note on notions of tape constructibility, Technical Report CSD-TR-187, Pennsylvania State University, 1976.
,21. Hierarchies of memory limited computations, Proc. of 1965 IEEE Conference Record on Switching Circuit Theory and Logical Design, 1965, pp. 179-190. | Zbl
, and ,22. The method of forced enumeration for nondeterministic automata, Acta Informatica, 1988, 26, pp. 279-284. | MR | Zbl
,23. Some remarks on the alternating hierarchy and closure under complement for sublogarithmic space, Information Processing Letters, 1989, 33, pp. 73-78. | MR | Zbl
,24. ∑2-SPACE (n) is closed under complement J. Comput Syst. Sciences, 1987, 35, pp. 145-152. | MR | Zbl
,25. Separating the polynomial time hierarchy by oracles, Proc. of 26th FOCS, 1985, pp. 1-10.
,