Space-bounded simulation of multitape turing machines

Leonard M. Adleman; Michael C. Loui

doi:10.1007/bf01752397

journal article Dec 01, 1981

Space-bounded simulation of multitape turing machines

Leonard M. Adleman Michael C. Loui

Mathematical Systems Theory Vol. 14 No. 1 pp. 215-222 · Springer Science and Business Media LLC

View at Publisher Save 10.1007/bf01752397

Topics

No keywords indexed for this article. Browse by subject →

References

7

[1]

J. Hopcroft, W. Paul, and L. Valiant, On time versus space,J. ACM, 24, 332–337 (1977). 10.1145/322003.322015

[2]

J. E. Hopcroft and J. D. Ullman, Relations between time and tape complexities,J. ACM, 15, 414–427 (1968). 10.1145/321466.321474

[3]

J. E. Hopcroft and J. D. Ullman,Formal Languages and their Relation to Automata, Addison-Wesley, Reading, Mass., 1969.

[4]

M. S. Paterson, Tape bounds for time-bounded Turing machines,J. Comp. Sys. Sci., 6, 116–124 (1972). 10.1016/s0022-0000(72)80017-5

[5]

M. S. Paterson, M. J. Fischer, and A. R. Meyer, An improved overlap argument for on-line multiplication,Complexity of Computation, SIAM-AMS Proc. vol. 7, ed. R. Karp, Amer. Math. Soc., 1974, pp. 97–111.

[6]

W. J. Paul and R. Reischuk, On time versus space II,Proc. 20th Ann. Symp. on Foundations of Computer Science, 1979, pp. 298–206. 10.1109/sfcs.1979.30

[7]

R. Reischuk, A fast implementation of a multidimensional storage into a tree storage,Proc. 7th Intern. Colloq. on Automata, Languages, and Programming, Springer-Verlag, 1980, pp. 531–542. 10.1007/3-540-10003-2_96

Cited By

7

On time versus space III

Joseph Y. Halpern, Michael C. Loui · 1986

Mathematical Systems Theory

Metrics

7

Citations

7

References

Details

Published: Dec 01, 1981
Vol/Issue: 14(1)
Pages: 215-222
License: View

Authors

L

Leonard M. Adleman

Department of Computer Science and Institute for Molecular Medicine and Technology, University of Southern California, Los Angeles, CA 90089, USA.

M

Michael C. Loui

Cite This Article

Leonard M. Adleman, Michael C. Loui (1981). Space-bounded simulation of multitape turing machines. Mathematical Systems Theory, 14(1), 215-222. https://doi.org/10.1007/bf01752397

Space-bounded simulation of multitape turing machines

You May Also Like