Abstract
It is shown 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. The proof is an offshoot of work in first-order expressibility.