|
|||||
|
|
Matching upper and lower bounds for simulations of several linear tapes on one multidimensional tape |
|
| Authors: | M. Dietzfelbinger M. Hühne |
| Affiliation: | Fachbereich Informatik, Lehrstuhl II, Universit?t Dortmund, D-44221 Dortmund, Germany, e-mail: Dietzfelbinger@informatik.uni-dortmund.de, DE Fachbereich Informatik, Lehrstuhl II, Universit?t Dortmund, D-44221 Dortmund, Germany, e-mail: Martin.Huehne@informatik.uni-dortmund.de, DE |
| Abstract: | We prove an O(t(n) d (t(n)) ? / log t(n)) time bound for the sim-ulation of t(n) steps of a Turing machine using several one-dimensional work tapes on a Turing machine using one d-dimensional work tape, . We prove a matching lower bound which holds for the problem of recognizing languages on machines with a separate one-way input tape. Received: March 1995. |
| Keywords: | . Computational complexity d-dimensional Turing machines simulation lower bounds Kolmogorov complexity. |
| 本文献已被 SpringerLink 等数据库收录！ | |