Speedup of determinism by alternation for multidimensional Turing machines
- Mak, Louis
Publication date
November 1994
DOI Publisher
Published by Elsevier B.V. ISSN
0304-3975Abstract
AbstractIn 1985, Dymond and Tompa showed that every deterministic Turing machine with linear tapes and time complexity T can be simulated by an alternating Turing machine with linear tapes that runs in time O(Tlog T). We extend their result to multidimensional Turing machines. We show that every deterministic Turing machine with d-dimensional tapes and time complexity T can be simulated by an alternating Turing machine with linear tapes that runs in time O(T(log T)1d
Add to ORKG