Journal of the ACM Bibliography

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.

Shortcuts: