Geodesic
A hierarchy that does not collapse : alternations in low level space
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 28 (1994) no. 5, pp. 465-512.

Voir la notice de l'article provenant de la source Numdam

@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://geodesic.mathdoc.fr/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://geodesic.mathdoc.fr/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://geodesic.mathdoc.fr/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, Tome 28 (1994) no. 5, pp. 465-512. http://geodesic.mathdoc.fr/item/ITA_1994__28_5_465_0/

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. | Zbl | MR

2. T. Baker, J. Gill and R. Solovay, Relativizations of the P =?NP question, SIAM J. Comput., 1975, 4(4), pp. 431-442. | Zbl | MR

3. B. Von Braunmuhl, Alternation for two-way machines with sublogarithmic space, to appear in Proc. of STACS'93. | Zbl | MR

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. | MR

5. A. K. Chandra, D. Kozen and L. J. Stockmeyer, Alternation, J. Assoc. Comput. Mach., 1981, 28, pp.114-133. | Zbl | MR

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). | Zbl | MR

7. A. R. Freedman and R. E. Ladner, Space bounds for processing contentless inputs, J. Comput. Syst. Sciences, 1975, 11, pp.118-128. | Zbl | MR

8. V. Geffert, Nondeterministic computations in sublogarithmic space and space constructibility, SIAM J. Comput., 1991, 20(3), pp. 484-498. | Zbl | MR

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. | Zbl | MR | mathdoc-id

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. | Zbl | MR

11. J. Hartmanis, The collapsing hierarchies, EATCS Bulletin, 1987, 33, pp. 26-39. | Zbl

12. L. A. Hemachandra, The strong exponential hierarchy collapses, Proc. of 19th ACM STOC Conference, 1987, pp.110-122.

13. N. Immerman, Nondeterministic space is closed under complement, SIAM J. Comput., 1988, 17, pp. 935-938. | Zbl | MR

14. K. Iwama, ASPACE( o (log log)) is regular, SIAM J. Comput., 1983, 22(1), pp. 136-146. | Zbl | MR

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. | Zbl | MR

16. M. Liśkiewicz and R. Reischuk, Separating the lower levels of the sublogarithmic space hierarchy, to appear in Proc. of STACS'93. | Zbl | MR

17. M. Liśkiewicz and R. Reischuk, The sublogarithmic space hierarchy is infinite, Technical Report, Technical University of Darmstadt, 1993.

18. D. Ranjan, R. Chang and J. Hartmanis, Space bounded computations: Review and new separation results, Theoret. Comp. Sci., 1991, 80, pp. 289-302. | Zbl | MR

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. | Zbl | MR

20. J. Seiferas, A note on notions of tape constructibility, Technical Report CSD-TR-187, Pennsylvania State University, 1976.

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

22. R. Szelepcsényi, The method of forced enumeration for nondeterministic automata, Acta Informatica, 1988, 26, pp. 279-284. | Zbl | MR

23. A. Szepietowski, Some remarks on the alternating hierarchy and closure under complement for sublogarithmic space, Information Processing Letters, 1989, 33, pp. 73-78. | Zbl | MR

24. S. Toda, ∑2-SPACE (n) is closed under complement J. Comput Syst. Sciences, 1987, 35, pp. 145-152. | Zbl | MR

25. A. Yao, Separating the polynomial time hierarchy by oracles, Proc. of 26th FOCS, 1985, pp. 1-10.