On non-determinacy in simple computing devices. (English) Zbl 0229.68014


68Q05 Models of computation (Turing machines, etc.) (MSC2010)
Full Text: DOI


[1] Ginsburg, S.: The mathematical theory of context-free languages. New York: McGraw-Hill 1966. · Zbl 0184.28401
[2] Hopcroft, J. E., Ullman, J. D.: Formal languages and their relation to automata. Addison-Wesley, Reading, Mass., 1969. · Zbl 0196.01701
[3] Savitch, W. J.: Nondederministic tape-bounded Turing machines: Doctorial thesis, Univ. of Calif., Berkeley, Calif., 1969.
[4] Hartmanis, J., Lewis II, P. M., Stearns, R. E.: Hierarchies of memory limited computations. IEEE Conference Record on Switching Circuit Theory and Logical Design, Ann Arbor, Michigan, p. 179-190, 1965. · Zbl 0229.02033
[5] Hennie, F. C., Stearns, R. E.: Two-tape simulation of multi-tape Turing machines. JACM 13, 533-546 (1966). · Zbl 0148.24801
[6] Rabin, M. O.: Real time computation. Israel J. Math. 1, 203-211 (1964). · Zbl 0156.25603
[7] Hartmanis, J., Hopcroft, J. E.: An overview of the theory of computational complexity. JACM 18, 444-475 (1971). · Zbl 0226.68024
[8] Hartmanis, J., Stearns, R. E.: On the computational complexity of algorithms. Trans. Amer. Math. Soc. 117, 285-306 (1965). · Zbl 0131.15404
[9] Hartmanis, J.: Computational complexity of random access stored program machines. J. Math. Systems Theory 5, 232-245 (1971). · Zbl 0222.68020
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.