On alternation
Wolfgang J. Paul, Ernst J. Praub, Rüdiger Reischuk · 1978
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.