Title :
Nondeterministic space is closed under complementation
Author_Institution :
Dept. Comput. Sci., Yale Univ., New Haven, CT, USA
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 :
context-sensitive languages; complementation; context-sensitive languages; first-order expressibility; nondeterministic space; Computer science; Counting circuits; History; Logic; Magnetic heads; Testing;
Conference_Titel :
Structure in Complexity Theory Conference, 1988. Proceedings., Third Annual
Conference_Location :
Washington, DC
Print_ISBN :
0-8186-0866-8
DOI :
10.1109/SCT.1988.5270
