Geodesic
A Turing machine space hierarchy
Kybernetika, Tome 15 (1979) no. 2, pp. 100-121 Cet article a éte moissonné depuis la source Czech Digital Mathematics Library

Voir la notice de l'article

Classification : 03D10, 03D15, 68C40, 68Q05, 68Q25 
@article{KYB_1979_15_2_a2,
     author = {\v{Z}\'ak, Stanislav},
     title = {A {Turing} machine space hierarchy},
     journal = {Kybernetika},
     pages = {100--121},
     year = {1979},
     volume = {15},
     number = {2},
     mrnumber = {542056},
     zbl = {0421.68050},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/KYB_1979_15_2_a2/}
}
TY  - JOUR
AU  - Žák, Stanislav
TI  - A Turing machine space hierarchy
JO  - Kybernetika
PY  - 1979
SP  - 100
EP  - 121
VL  - 15
IS  - 2
UR  - http://geodesic.mathdoc.fr/item/KYB_1979_15_2_a2/
LA  - en
ID  - KYB_1979_15_2_a2
ER  - 
%0 Journal Article
%A Žák, Stanislav
%T A Turing machine space hierarchy
%J Kybernetika
%D 1979
%P 100-121
%V 15
%N 2
%U http://geodesic.mathdoc.fr/item/KYB_1979_15_2_a2/
%G en
%F KYB_1979_15_2_a2
Žák, Stanislav. A Turing machine space hierarchy. Kybernetika, Tome 15 (1979) no. 2, pp. 100-121. http://geodesic.mathdoc.fr/item/KYB_1979_15_2_a2/

[1] J. H. Hopcroft J. D. Ullman: Formal Languages and their Relation to Automata. Adison-Wesley, Reading, Mass. 1969.

[2] H. Rogers, Jr.: Theory of Recursive Functions and Effective Computability. McGraw-Hill, New York 1967. | MR | Zbl

[3] J. I. Seiferas: Nondeterministic time and space complexity classes. Project MAC, TR-137, 1974.

[4] J. I. Seiferas: Techniques for separating space complexity classes. JCSS 14 (1977) 1, 73 - 99. | MR | Zbl

[5] I. H. Sudborough: Separating tape bounded auxiliary pushdown automata classes. Proceedings of the Ninth Annual ACM Symposium on Theory of Computing, Boulder, Colorado, May 2-4, 1977, pp. 208 - 217. | MR

[6] B. A. Trachtenbrot: Optimal computations and the frequency phenomenon of Jablonskij. (In Russian.) Algebra i Logika (Seminar) 4/5 (1965), 79 - 83. | MR

[7] B. A. Trachtenbrot: About normed signaling functions of computations on Turing machines. (In Russian.) Algebra i Logika 5/6 (1966), 61-70. | MR

[8] S. Žák: Functions realizable on Turing machines with bounded memory. (In Czech.) 1975, unpublished, Master thesis, Faculty of Mathematics and Physics, Charles University.

[9] S. Žák: A space hierarchy of languages. (In Czech.) 1977, unpublished, RNDr thesis, Faculty of Mathematics and Physics, Charles University.