Nondeterministic Space is Closed under Complementation

Abstract

In this paper we show that nondeterministic space $s(n)$ is closed under complementation for $s(n)$ greater than or equal to $\log n$. It immediately follows that the context-sensitive languages are closed under complementation, thus settling a question raised by Kuroda [Inform. and Control, 7 (1964), pp. 207–233].