Additional Key Words and Phrases: Turing machine, computational complexity, tape complexity, off-line Turing machine, on-line Turing machine, nondeterministic Turing machine, transition matrix
Selected papers that cite this one
- José L. Balcázar, Josep Díaz, and Joaquim Gabarró Uniform characterizations of non-uniform complexity measures. Information and Control, 67(1-3):53-69, October/November/December 1985.
- Viliam Geffert. Bridging across the log(n) space frontier. Information and Computation, 142(2):127-158, 1 May 1998.
- S. A. Greibach. Remarks on the complexity of nondeterministic counter languages. Theoretical Computer Science, 1(4):269-288, April 1976.
- Oscar H. Ibarra. A note concerning nondeterministic tape complexities. Journal of the ACM, 19(4):608-612, October 1972.
- Akira Ito, Katsushi Inoue, Itsuo Takanami, and Hiroshi Taniguchi. Two-dimensional alternating Turing machines with only universal states. Information and Control, 55(1-3):193-221, October/November/December 1982.
- Kenneth W. Regan. Diagonalization, uniformity, and fixed-point theorems. Information and Computation, 98(1):1-40, May 1992.
- J. D. Ullman. Halting stack automata. Journal of the ACM, 16(4):550-563, October 1969.
Selected references
- P. M. Lewis II, R. E. Stearns, and J. Hartmanis. Memory bounds for recognition of context-free and context-sensitive languages. In Proceedings of the Sixth Annual Symposium on Switching Circuit Theory and Logical Design, pages 191-202. IEEE, 1965.
- R. E. Stearns, J. Hartmanis, and P. M. Lewis II. Hierarchies of memory limited computations. In Proceedings of the Sixth Annual Symposium on Switching Circuit Theory and Logical Design, pages 179-190. IEEE, 1965.