| Title:
|
A Turing machine space hierarchy (English) |
| Author:
|
Žák, Stanislav |
| Language:
|
English |
| Journal:
|
Kybernetika |
| ISSN:
|
0023-5954 |
| Volume:
|
15 |
| Issue:
|
2 |
| Year:
|
1979 |
| Pages:
|
(100)-121 |
| . |
| Category:
|
math |
| . |
| MSC:
|
03D10 |
| MSC:
|
03D15 |
| MSC:
|
68C40 |
| MSC:
|
68Q05 |
| MSC:
|
68Q25 |
| idZBL:
|
Zbl 0421.68050 |
| idMR:
|
MR542056 |
| . |
| Date available:
|
2009-09-24T17:06:32Z |
| Last updated:
|
2012-06-05 |
| Stable URL:
|
http://hdl.handle.net/10338.dmlcz/124477 |
| . |
| Reference:
|
[1] J. H. Hopcroft J. D. Ullman: Formal Languages and their Relation to Automata.Adison-Wesley, Reading, Mass. 1969. |
| Reference:
|
[2] H. Rogers, Jr.: Theory of Recursive Functions and Effective Computability.McGraw-Hill, New York 1967. Zbl 0183.01401, MR 0224462 |
| Reference:
|
[3] J. I. Seiferas: Nondeterministic time and space complexity classes.Project MAC, TR-137, 1974. |
| Reference:
|
[4] J. I. Seiferas: Techniques for separating space complexity classes.JCSS 14 (1977) 1, 73 - 99. Zbl 0352.68062, MR 0495207 |
| Reference:
|
[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 |
| Reference:
|
[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 |
| Reference:
|
[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 |
| Reference:
|
[8] S. Žák: Functions realizable on Turing machines with bounded memory.(In Czech.) 1975, unpublished, Master thesis, Faculty of Mathematics and Physics, Charles University. |
| Reference:
|
[9] S. Žák: A space hierarchy of languages.(In Czech.) 1977, unpublished, RNDr thesis, Faculty of Mathematics and Physics, Charles University. |
| . |
