Preliminary versionA preliminary version of these results was presented in: 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.
Selected papers that cite this one
- Tao Jiang, Joel I. Seiferas, and Paul M. B. Vitányi. Erratum: ``Two heads are better than two tapes''. Journal of the ACM, 44(4):632, July 1997.
Selected references
- Pavol D\=uri\=s, Zvi Galil, Wolfgang Paul, and Ruediger Reischuk. Two nonlinear lower bounds for on-line computations. Information and Control, 60(1-3):1-11, January/February/March 1984.
- Patrick C. Fischer, Albert R. Meyer, and Arnold L. Rosenberg. Real-time simulation of multihead tape units. Journal of the ACM, 19(4):590-607, October 1972.
- Benton L. Leong and Joel I. Seiferas. New real-time simulations of multihead tape units. Journal of the ACM, 28(1):166-180, January 1981.
- Ming Li, Luc Longpré, and Paul Vitányi. The power of the queue. SIAM Journal on Computing, 21(4):697-712, August 1992.
- Ming Li and Paul M. B. Vitányi. Tape versus queue and stacks: The lower bounds. Information and Computation, 78(1):56-85, July 1988.
- 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.
- Ramamohan Paturi, Joel I. Seiferas, Janos Simon, and Richard E. Newman-Wolfe. Milking the Aanderaa argument. Information and Computation, 88(1):88-104, September 1990.
- W. Paul. On-line simulation of k+1 tapes by k tapes requires nonlinear time. Information and Control, 53(1/2):1-8, April/May 1982.
- W. Paul. On heads versus tapes. Theoretical Computer Science, 28(1-2):1-12, January 1984.
- Wolfgang Paul, Joel I. Seiferas, and Janos Simon. An information-theoretic approach to time bounds for on-line computation. Journal of Computer and System Sciences, 23(2):108-126, October 1981.
- H.-J. Stoss and W. Schnitzlein. Linear-time simulation of multihead Turing machines. Information and Computation, 81(3):353-363, June 1989.
- Paul M. B. Vitányi. On two-tape real-time computation and queues. Journal of Computer and System Sciences, 29(3):303-311, December 1984.