Additional Key Words and Phrases: computational complexity, real-time computation, multihead tape units, multitape Turing machine, simulation, buffer
Selected papers that cite this one
- Tao Jiang, Joel I. Seiferas, and Paul M. B. Vitányi. Two heads are better than two tapes. Journal of the ACM, 44(2):237-256, March 1997.
- Tao Jiang, Joel I. Seiferas, and Paul M. B. Vitányi. Two heads are better than two tapes. In Proceedings of the Twenty-Sixth Annual ACM Symposium on the Theory of Computing, pages 668-675, Montréal, Québec, Canada, 23-25 May 1994.
- Haim Kaplan and Robert E. Tarjan. Persistent lists with catenation via recursive slow-down. In Proceedings of the Twenty-Seventh Annual ACM Symposium on the Theory of Computing, pages 93-102, Las Vegas, Nevada, 29 May-1 June 1995.
- Chris Okasaki. Simple & Efficient purely functional Queues and Deques Journal of Functional Programming, 5(4):583-592 October 1995
- Nicholas Pippenger. Pure versus impure LISP. In Conference Record of POPL '96: The 23rd ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, pages 104-109, St. Petersburg Beach, Florida, 21-24 January 1996.
- Kenneth W. Regan. Linear time and memory-efficient computation. SIAM Journal on Computing, 25(1):133-168, February 1996.
Selected references
- Patrick C. Fischer. Turing machines with restricted memory access. Information and Control, 9(4):364-379, August 1966.
- Patrick C. Fischer. Turing machines with a schedule to keep. Information and Control, 11(1/2):138-146, July-August 1967.
- Michael J. Fischer and Arnold L. Rosenberg. Limited random access Turing machines. In Conference Record of 1968 Ninth Annual Symposium on Switching and Automata Theory, pages 356-367, Schenectady, New York, 15-18 October 1968. IEEE.
- Albert R. Meyer, Arnold L. Rosenberg, and Patrick C. Fischer. Turing machines with several read-write heads (preliminary report). In Conference Record of 1967 Eighth Annual Symposium on Switching and Automata Theory, pages 117-127, Austin, Texas, 18-20 October 1967. IEEE.
- Arnold L. Rosenberg. Real-time definable languages. Journal of the ACM, 14(4):645-662, October 1967.