Some observations concerning alternating Turing machines using small space. (English) Zbl 0635.68040

Summary: We make some observations concerning alternating Turing machines operating in small space. For example, we show that alternating Turing machines using o(log n) space are more powerful than nondeterministic Turing machines using the same space-bound. In fact, we show that there is a language over a unary alphabet that can be accepted by an on-line alternating Turing machine in log log n space, but not by any off-line nondeterministic Turing machine in o(log n) space. We also investigate the weak vs. strong space bounds and on-line vs. off-line machines at these low tape bounds.


68Q05 Models of computation (Turing machines, etc.) (MSC2010)
Full Text: DOI


[1] Alberts, M., Space complexity of alternating Turing machines, (Lecture Notes in Computer Science: Fundamentals of Computation Theory (1986), Springer: Springer Berlin), 1-7
[2] Alt, H.; Melhorn, K., A language over a one symbol alphabet requiring only O(log log \(n)\) space, SIGACT Newslett., 31-33 (1975)
[3] Alt, H.; Melhorn, K., Lower bounds for the space complexity of context-free recognition, (Proc. 3rd Coll. on Automata, Languages and Programming (1976), Springer: Springer Berlin), 339-354 · Zbl 0368.68069
[4] Chandra, A.; Kozen, D.; Stockmeyer, L., Alternation, J. ACM, 28, 114-133 (1981) · Zbl 0473.68043
[5] Cook, S. A., Characterizations of pushdown machines in terms of time-bounded computers, J. ACM, 18, 4-18 (1971) · Zbl 0222.02035
[6] Freedman, A.; Ladner, R., Space bounds for processing contentless inputs, J. Comput. System Sci., 11, 118-128 (1975) · Zbl 0307.68036
[7] Freivalds, R., On time complexity of deterministic and nondeterministic Turing machines, Latvian Math., 23, 158-165 (1979) · Zbl 0462.68028
[8] Hartmanis, J.; Berman, L., Tape bounds for processing languages over unary alphabet, Theoret. Comput. Sci., 3, 213-224 (1976) · Zbl 0351.68014
[9] Hartmanis, J.; Lewis, P.; Stearns, R., Hierarchies of memory limited computations, (Proc. 6th Ann. IEEE Symp. on Switching Theory and Logical Design (1965)), 179-190 · Zbl 0229.02033
[10] Hopcroft, J. E.; Ullman, J. D., Some results on tape-bounded Turing machines, J. ACM, 16, 168-177 (1969) · Zbl 0188.33501
[11] Inoue, K.; Takanami, J.; Vollmar, R., Alternating on-line Turing machines with only universal states and small space bounds (Note), Theoret. Comput. Sci., 41, 2,3, 331-339 (1985) · Zbl 0604.68056
[12] Korenjak, A.; Hopcroft, J. E., Simple deterministic languages, (IEEE 7th Ann. Symp. on Switching and Automata Theory (1966)), 36-46 · Zbl 0313.68061
[13] Sipser, M., Halting space-bounded computations, Theoret. Comput. Sci., 10, 335-338 (1980) · Zbl 0423.68011
[14] Sudborough, I., Efficient algorithms for path system problems and applications to alternating and time-space complexity classes, (Proc. 21st Ann. Symp. on Foundations of Computer Science (1980)), 62-73
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.