Tally versions of the Savitch and Immerman-Szelepcsényi theorems for sublogarithmic space. (English) Zbl 0766.68039

Summary: It is shown that for each \(s(n)\)-space-bounded nondeterministic Turing machine recognizing a language \(L\subseteq 1^*\) there exists an equivalent deterministic \(O(s^ 2(n))\)-space-bounded machine, and also a nondeterministic \(O(s(n))\)-space-bounded machine recognizing the complement of \(L\), for any \(s(n)\), independent of whether \(s(n)\) is below \(\log(n)\) or is space constructible. In other words, the W. J. Savitch [J. Comput. System Sci. 4, 177-192 (1970)] N. Immerman and R.Szelepcsényi [SIAM J. Comput. 17, 935-938 (1988; Zbl 0668.68056); Acta Inform. 26, 279-284 (1988; Zbl 0649.68055)] theorems can be extended to any space bound \(s(n)\) for languages over a single-letter alphabet.


68Q15 Complexity classes (hierarchies, relations among complexity classes, etc.)
68Q45 Formal languages and automata
68Q05 Models of computation (Turing machines, etc.) (MSC2010)
Full Text: DOI