Summary
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 (n + (t(n)) 1/2)-timebounded 1-tape Turing machine. For wellbehaved functions t(n) every nondeterministic t(n)-time bounded 1-tape Turing machine can be simulated by a deterministic ((nlogn)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.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Bermann L (1977) Precise bound for Presburger arithmetic and the reals with addition. 18th IEEE-FOCS, 95–99
Book RV, Greibach SA, Wegbreit B (1970) Time and tape bounded Turing acceptors and AFL's. J Comput System Sci 4:606–621
Chandra A, Stockmeyer L (1976) Alternation, 17th IEEE-FOCS, 98–108
Erdös P, Graham R, Szemeredi E (1975) Sparse graphs with dense long paths. STAN-CS-75-504, Computer Science Dept, Stanford MA
Fischer MJ, Ladner RE (1977) Propositional modal logic of programs. 9th ACM-STOC, 286–294
Hartmanis J (1965) Size arguments in the study of computation speeds. Symp on Computers and Automata, Polytechnic Inst of Brooklyn, 1–18
Hartmanis J, Lewis PM, Stearns RE (1965) Hierarchies of memory limited computations. 6th IEEE Symposium on Switching Circuit Theory and Logical Design, 179–190
Hennie FC (1965) One-tape off-line Turing machine computations. Information and Control 8: 553–578
Hopcroft JE, Paul WJ, Vailant LG (1977) On time versus space. J ACM 24: 332–337
Kozen D (1976) On parallelism in Turing machines. 17th IEEE-FOCS, 89–97
Lipton R, Tarjan R (1977) Applications of a planar separator theorem. 18th IEEE-FOCS, 162–170
Monien B (1977) About the derivation languages of grammars and machines. Proc. 3rd ICALP, Lecture notes in Computer Science
Paterson M (1972) Tape bounds for time-bounded Turing machines. J Comput System Sci 6: 116–124
Pippenger N, Fischer M (1979) Relations among complexity measures, J. ACM 26:361–381
Author information
Authors and Affiliations
Additional information
A preliminary version of this paper was presented at the 19th IEEE-FOCS
Rights and permissions
About this article
Cite this article
Paul, W.J., Prauß, E.J. & Reischuk, R. On alternation. Acta Informatica 14, 243–255 (1980). https://doi.org/10.1007/BF00264255
Received:
Revised:
Issue Date:
DOI: https://doi.org/10.1007/BF00264255