Journal of the ACM Bibliography

Additional Key Words and Phrases: Turing machines, multistage Turing machines, time-bounded computers, abstract computer models, pushdown automata, multihead pushdown automata, stack automata, writing pushdown accepotrs, auxiliary pushdown machines, computational complexity

Selected papers that cite this one

• Eric Allender, Jia Jiao, Meena Mahajan, and V. Vinay. Non-commutative arithmetic circuits: depth reduction and size lower bounds. Theoretical Computer Science, 209(1-2):47-86, 6 December 1998. Fundamental Study.

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

• Ronald V. Book. Translational lemmas, polynomial time, and (log n)^j-space. Theoretical Computer Science, 1(3):215-226, February 1976.

• Ronald V. Book. On languages accepted in polynomial time. SIAM Journal on Computing, 1(4):281-287, December 1972.

• Allan Borodin, Stephen A. Cook, Patrick W. Dymond, Walter L. Ruzzo, and Martin Tompa. Two applications of inductive counting for complementation problems. SIAM Journal on Computing, 18(3):559-578, June 1989.

• Gerhard Buntrock, Lane A. Hemachandra, and Dirk Siefkes. Using inductive counting to simulate nondeterministic computation. Information and Computation, 102(1):102-117, January 1993.

• S. A. Greibach. Remarks on the complexity of nondeterministic counter languages. Theoretical Computer Science, 1(4):269-288, April 1976.

• C. Lautemann, T. Schwentick, and I. A. Stewart. Positive versions of polynomial time. Accepted for publication in Information and Computation. Final manuscript received for publication May 17, 1998.

• Ioan I. Macarie and Mitsunori Ogihara. Properties of probabilistic pushdown automata. Theoretical Computer Science, 207(1):117-130, 28 October 1998.

• Rolf Niedermeier and Peter Rossmanith. Unambiguous auxiliary pushdown automata and semi-unbounded fan-in circuits. Information and Computation, 118(2):227-245, 1 May 1995.

Selected references

• A. V. Aho, J. E. Hopcroft, and J. D. Ullman. Time and tape complexity of pushdown automaton languages. Information and Control, 13(3):186-206, September 1968.

• Stephen N. Cole. Real-time computation by n-dimensional iterative arrays of finite-state machines. In Conference Record of 1966 Seventh Annual Symposium on Switching and Automata Theory, pages 53-77, Berkeley, California, 26-28 October 1966. IEEE.

• Stephen A. Cook. Variations on pushdown machines (detailed abstract). In Conference Record of ACM Symposium on Theory of Computing, pages 229-231, Marina del Rey, California, 5-7 May 1969.

• Seymour Ginsburg, Sheila A. Greibach, and Michael A. Harrison. Stack automata and compiling. Journal of the ACM, 14(1):172-201, January 1967.

• James N. Gray, Michael A. Harrison, and Oscar H. Ibarra. Two-way pushdown automata. Information and Control, 11(1/2):30-70, July-August 1967.

• Michael A. Harrison and Oscar H. Ibarra. Multi-tape and multi-head pushdown automata. Information and Control, 13(5):433-470, November 1968.

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

• Donald E. Knuth and Richard H. Bigelow. Programming language for automata. Journal of the ACM, 14(4):615-635, October 1967.

• J. C. Shepherdson and H. E. Sturgis. Computability of recursive functions. Journal of the ACM, 10(2):217-255, April 1963.

Shortcuts: