Remarks on languages acceptable in log log n space. (English) Zbl 0652.68055
A language is acceptable in the strong sense by a two-way nondeterministic Turing machine when all computation paths on every input stop and satisfy the space bound. The following main theorem is established. There exists a language which is acceptable in the strong sense by a two-way nondeterministic Turing machine in log log n space such that: if the language is not decidable by any two-way deterministic Turing machine in log log n space, then \(L\neq NL\).
Reviewer: Lih Ko-Wei
MSC:
| 68Q25 | Analysis of algorithms and problem complexity |
| 68Q05 | Models of computation (Turing machines, etc.) (MSC2010) |
| 68Q45 | Formal languages and automata |
References:
| [1] | Alberts, M., Space complexity of alternating Turing machines, (Budach, L., Fundamentals of Computing Theory, FCT’85 Conf., Vol. 199 (1985), Springer: Springer Berlin), 1-7, Lecture Notes in Computer Science · Zbl 0574.68040 |
| [2] | Freivalds, R., On time complexity of deterministic and nondeterministic Turing machines, Latvian Mathematics, 23, 158-165 (1979), (in Russian) · Zbl 0462.68028 |
| [3] | Lewis, P. M.; Stearns, R. E.; Hartmanis, J., Memory bounds for recognition of context-free and context-sensitive languages, IEEE Conf. Rec. on Switching Circuit Theory and Logic Design, 191-202 (1965) · Zbl 0272.68054 |
| [4] | Sierpiński, W., Elementary Theory of Numbers, Monografie Matematyczne, Vol. 42 (1964), PWN: PWN Warszawa · Zbl 0638.10001 |
| [5] | Stearns, R. E.; Hartmanis, J.; Lewis, P. M., Hierarchies of memory limited computations, IEEE Conf. Rec. on Switching Circuit Theory and Logic Design, 179-190 (1965) · Zbl 0229.02033 |
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.
