Author :
Paul, Wolfgang J. ; Praub, Ernst J. ; Reischuk, Rüdiger
Abstract :
Every alternating t(n) -time bounded multitape Turing machine can be simulated by an alternating t(n) -time bounded 1-tape Turing machine. Every nondeterministic t(n) -time bounded 1-tape Turing machine can be simulated by an alternating O(n+(t(n))1/2) -time bounded 1-tape Turing machine. For well-behaved functions t(n) every nondeterministic t(n) -time bounded 1-tape Turing machine can be simulated by a deterministic ((n log n)1/2 + (t(n))1/2) -tape bounded off-line Turing machine. These results improve or extend results by Chandra-Stockmeyer, Lipton-Tarjan and Paterson.
Keywords :
Helium; Particle separators; Testing; Turing machines;
Conference_Titel :
Foundations of Computer Science, 1978., 19th Annual Symposium on
Conference_Location :
Ann Arbor, MI, USA
DOI :
10.1109/SFCS.1978.24
