| Real-Time Simulation of Multihead Tape Units |
| Full text |
 Pdf
(1.26 MB)
|
| Source
|
Journal of the ACM (JACM)
archive
Volume 19 , Issue 4 (October 1972)
table of contents
Pages: 590 - 607
Year of Publication: 1972
ISSN:0004-5411
|
|
Authors
|
|
Patrick C. Fischer
|
University of Waterloo, Department of Applied Analysis and Computer Science, Waterloo, Ontario, Canada
|
|
Albert R. Meyer
|
Massachusetts Institute of Technology, Project MAC, 545 Technology Square, Cambridge, MA
|
|
Arnold L. Rosenberg
|
IBM Thomas J. Watson Research Center, Yorktown Heights, New York
|
|
| Publisher |
|
| Bibliometrics |
Downloads (6 Weeks): 3, Downloads (12 Months): 26, Citation Count: 20
|
|
|
 REFERENCES
Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.
| |
1
|
FISCHER, P .C . Turing machines with restricted memory access. Information and Control 9, 4 (Aug. 1966), 364-379.
|
| |
2
|
FISCHER, P. C. Turing machines with a schedule to keep. Inrormation and Control 11, 1-2 (July-Aug. 1967), 138-146.
|
| |
3
|
FISCHER, P. C., MEYER, A. I~., AND I~OSENBERG, A .L . Counter machines and counter languages. Math. Systems Theory P, 3 (Sept. 1968), 265-283.
|
| |
4
|
FISCHER, P. C., MEYER, A. R., AND ROSENBERG, A.L. Time-restricted sequence generation. J. Comp. Syst. Sci. 4, 1 (Feb. 1970), 50-73.
|
| |
5
|
FISCHER, M. J., AND ROSENBERG, A. L. Limited random access Turing machines. Proc. Ninth Ann. Symp. on Switching and Automata Theory, IEEE, 1968, pp. 356-367.
|
| |
6
|
HARTMANIS, J., AND STEARNS, R. E. On the computational complexity of algorithms. Trans. Amer. Math. Soc. 117, 5 (May 1965), 285-306.
|
| |
7
|
HENNIE, F .C . On-line Turing machine computations. IEEE Trans. EC-15, 1 (Feb. 1966), 35-44.
|
| |
8
|
MEYER, A.R. An optimal time bound for a one-tapeon-line Turingmachinecomputation. IEEE Trans. Computers (to appear).
|
| |
9
|
MEYER, A. R., ROSENBERG, A. L., AND FISCHER, P.C. Multitapesimulationo{ multihead Turing machines. Proc. Eighth Ann. Symp. on Switching and Automata Theory, IEEE, 1967, pp. 117-127.
|
 |
10
|
|
| |
11
|
STOSS, H .J . k-Band-Simulation yon k-Kopf-Turing-Maschinen. Computing 6, 3 (1970), 309-317.
|
| |
12
|
YAMADA, H. Real-time computation and recursive functions not real-time computable. IRE Trans. EC-11 (Dec. 1962), 753-760. Corr. ibid: EC-12 (Aug. 1963), 400.
|
CITED BY 20
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Tao Jiang , Joel I. Seiferas , Paul M. B. Vitányi, Two heads are better than two tapes, Proceedings of the twenty-sixth annual ACM symposium on Theory of computing, p.668-675, May 23-25, 1994, Montreal, Quebec, Canada
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Wolfgang J. Paul , Joel I. Seiferas , Janos Simon, An information-theoretic approach to time bounds for on-line computation (preliminary version), Proceedings of the twelfth annual ACM symposium on Theory of computing, p.357-367, April 28-30, 1980, Los Angeles, California, United States
|
|
|
|
|
|
|
|
|
Tyng-Ruey Chuang , Benjamin Goldberg, Real-time deques, multihead Turing machines, and purely functional programming, Proceedings of the conference on Functional programming languages and computer architecture, p.289-298, June 09-11, 1993, Copenhagen, Denmark
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Adobe Acrobat
QuickTime
Windows Media Player
Real Player
I.6