DocumentCode
2179303
Title
On alternation
Author
Paul, Wolfgang J. ; Praub, Ernst J. ; Reischuk, Rüdiger
fYear
1978
fDate
16-18 Oct. 1978
Firstpage
113
Lastpage
122
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;
fLanguage
English
Publisher
ieee
Conference_Titel
Foundations of Computer Science, 1978., 19th Annual Symposium on
Conference_Location
Ann Arbor, MI, USA
ISSN
0272-5428
Type
conf
DOI
10.1109/SFCS.1978.24
Filename
4567969
Link To Document