Journal of the ACM Bibliography

Additional Key Words and Phrases: computational complexity, complexity axioms, complexity measures, computation speed, time-bounds, tape-bounds, speed-up, Turing machines, diagonalization, length of programs

Selected papers that cite this one

• Leonard Bass and Paul Young. Ordinal hierarchies and naming complexity classes. Journal of the ACM, 20(4):668-686, October 1973.

• P. van Emde Boas. Some applications of the McCreight-Meyer algorithm in abstract complexity theory. Theoretical Computer Science, 7(1):79-98, August 1978.

• Robert L. Constable. A note on complexity measures for inductive classes in constructive type theory. Information and Computation, 143(2):137-153, 15 June 1998.

• Robert L. Constable and Allan B. Borodin. Subrecursive programming languages, part I: Efficiency and program structure. Journal of the ACM, 19(3):526-568, July 1972.

• Juris Hartmanis. Relations between diagonalization, proof systems, and complexity gaps. Theoretical Computer Science, 8(2):239-253, April 1979.

• David R. Luginbuhl and Michael C. Loui. Hierarchies and space measures for pointer machines. Information and Computation, 104(2):253-270, June 1993.

Selected references

• Manuel Blum. On effective procedures for speeding up algorithms. In Conference Record of ACM Symposium on Theory of Computing, pages 43-53, Marina del Rey, California, 5-7 May 1969.

• Manuel Blum. A machine-independent theory of the complexity of recursive functions. Journal of the ACM, 14(2):322-336, April 1967.

• Manuel Blum. On the size of machines. Information and Control, 11(3):257-265, September 1967.

• A. Borodin. Complexity classes of recursive functions and the existence of complexity gaps. In Conference Record of ACM Symposium on Theory of Computing, pages 67-78, Marina del Rey, California, 5-7 May 1969.

• A. Borodin, R. L. Constable, and J. E. Hopcroft. Dense and non-dense families of complexity classes. In Conference Record of 1969 Tenth Annual Symposium on Switching and Automata Theory, pages 7-19, Waterloo, Ontario, Canada, 15-17 October 1969. IEEE.

• Alan Cobham. On the Hartmanis-Stearns problem for a class of TAG machines. In Conference Record of 1968 Ninth Annual Symposium on Switching and Automata Theory, pages 51-60, Schenectady, New York, 15-18 October 1968. IEEE.

• Robert L. Constable. The operator gap. In Conference Record of 1969 Tenth Annual Symposium on Switching and Automata Theory, pages 20-26, Waterloo, Ontario, Canada, 15-17 October 1969. IEEE.

• Patrick C. Fischer, Juris Hartmanis, and Manuel Blum. Tape reversal complexity hierarchies. In Conference Record of 1968 Ninth Annual Symposium on Switching and Automata Theory, pages 373-382, Schenectady, New York, 15-18 October 1968. IEEE.

• J. Hartmanis. Computational complexity of one-tape Turing machine computations. Journal of the ACM, 15(2):325-339, April 1968.

• J. Hartmanis and R. E. Stearns. Computational complexity of recursive sequences. In Proceedings of the Fifth Annual Symposium on Switching Circuit Theory and Logical Design, pages 82-90, Princeton, New Jersey, 11-13 November 1964. IEEE.

• F. C. Hennie. Crossing sequences and off-line Turing machine computations. In Proceedings of the Sixth Annual Symposium on Switching Circuit Theory and Logical Design, pages 168-172. IEEE, 1965.

• F. C. Hennie. One-tape, off-line Turing machine computations. Information and Control, 8(6):553-578, December 1965.

• F. C. Hennie and R. E. Stearns. Two-tape simulation of multitape Turing machines. Journal of the ACM, 13(4):533-546, October 1966.

• John E. Hopcroft and Jeffrey D. Ullman. Relations between time and tape complexities. Journal of the ACM, 15(3):414-427, July 1968.

• Richard M. Karp. Some bounds on the storage requirements of sequential machines and Turing machines. Journal of the ACM, 14(3):478-489, July 1967.

• L. H. Landweber and E. L. Robertson. Recursive properties of abstract complexity classes (preliminary version). In Conference Record of Second Annual ACM Symposium on Theory of Computing, pages 31-36, Northampton, Massachusetts, 4-6 May 1970.

• F. D. Lewis. Unsolvability considerations in computational complexity. In Conference Record of Second Annual ACM Symposium on Theory of Computing, pages 22-30, Northampton, Massachusetts, 4-6 May 1970.

• 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.

• E. M. McCreight and A. R. Meyer. Classes of computable functions defined by bounds on computation: Preliminary report. In Conference Record of ACM Symposium on Theory of Computing, pages 79-88, Marina del Rey, California, 5-7 May 1969.

• Walter J. Savitch. Deterministic simulation of non-deterministic Turing machines (detailed abstract). In Conference Record of ACM Symposium on Theory of Computing, pages 247-248, Marina del Rey, California, 5-7 May 1969.

• 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.

• Paul R. Young. Toward a theory of enumerations. Journal of the ACM, 16(2):328-348, April 1969.

Shortcuts: