Nondeterministic space is closed under complementation

1 January 1988

conference paper
Published by Institute of Electrical and Electronics Engineers (IEEE)

p. 112-115
https://doi.org/10.1109/sct.1988.5270

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.

Keywords

COUNTING CIRCUITS
LOGIC
TESTING
COMPUTER SCIENCE
HISTORY
MAGNETIC HEADS

This publication has 0 references indexed in Scilit: