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

Problem Detail: 

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 ?

Asked By : arty

Answered By : Hendrik Jan

The first closure property, closure under intersection, is a DIY proof if you choose the right model for the context-sensitive languages. By defining them with the help of linear-bounded automata you can run two of these automata successively to test (nondeterministically) for acceptance of the intersection.

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.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/15014