About DML-CZ | FAQ | Conditions of Use | Math Archives | Contact Us
  Previous |  Up |  Next

Article

First Page Preview
Žák, Stanislav
A Turing machine space hierarchy. (English). Kybernetika, vol. 15 (1979), issue 2, pp. (100)-121
MSC: 03D10, 03D15, 68C40, 68Q05, 68Q25 | MR 542056 | Zbl 0421.68050
References:
[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 0224462 | Zbl 0183.01401
[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 0495207 | Zbl 0352.68062
[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 0483723
[6] B. A. Trachtenbrot: Optimal computations and the frequency phenomenon of Jablonskij. (In Russian.) Algebra i Logika (Seminar) 4/5 (1965), 79 - 83. MR 0194280
[7] B. A. Trachtenbrot: About normed signaling functions of computations on Turing machines. (In Russian.) Algebra i Logika 5/6 (1966), 61-70. MR 0231671
[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.
Partner of
EuDML logo