Tally Versions of the Savitch and Immerman–Szelepcsényi Theorems for Sublogarithmic Space

Abstract

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 Savitch [J. Comput. System Sci., 4(1970), pp. 177–192] and Immerman–Szelepcsényi [SIAM J. Comput., 17(1988), pp. 935–938], [Acts Inform., 26(1988), pp. 279–284] theorems can be extended to any space bound $s(n)$ for languages over a single-letter alphabet.