# How to prove that context sensitive languages are closed under intersection and complement?

This is a question from the exam of our "Automata and Formal Languages" course. There is a question where asked to prove or disprove that any "relative complement" operation between two context sensitive languages will also produce a context sensitive language.

From the context sensitive closure properties Wikipedia, and princeton.edu. I know that those languages are closed under intersection and complement.

I have spent too much time on finding the formal prove of those statements. Where / How can I find the proofs? Or how to prove them by myself? Can anyone point me to a reference ? Can any one post here the proofs ?

• Your question is not specific enough for this site. Tell us what you've tried and where you got stuck. The goal of education is to learn how to solve problems, not how to make other people solve your problems. – reinierpost Oct 14 '13 at 11:06
• i don't think your right, my question is very strict. I noted that i can't find a reference that proofs some of LCS closure properties. I didn't asked to solve the original question since i posted the solution also... – arty Oct 14 '13 at 11:47
• I think you may be right that the exact question isn't being answered there. – reinierpost Oct 14 '13 at 13:06

Second, closure under complement, is hard! It used to be a famous open problem until solved independently by Immerman and Szelepcsényi. It is quite a surprising proof, how to prove complement for a nondeterministic automaton. The technique is called inductive counting and works for larger families of complexity classes: NSPACE($s(n)$)=co-NSPACE($s(n)$), where context-sensitive equals linear nondeterministic space.