o n A 1 t ern a t ion (preliminary version)
Wolfgang J. Paul, Ernst J. Praub, Rüdiger Reischuk · 1978
Every alternating t(n) -time bounded mu1titape Turing machine can be simulated by an alternating t(n) -time bounded I-tape Turing machine. Every non deterministic t(n) -time bounded I-tape Turing machine can be simulated by an alter nating 0(n+(t(n»1/2) -time bounded I-tape Turing machine. For well-behaved functions t(n) every nondeterministic t(n) -time bounded I-tape Turing machine can be sim ulated by a deterministic «n log n)I/2 + (t(n»J/2) -tape bounded off-line Turing machine. These results im prove or extend results by Chandra-Stock meyer, Lipton-Tarjan and Paterson.