7
$\begingroup$

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 ?

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – reinierpost Oct 14 '13 at 11:06
  • $\begingroup$ 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... $\endgroup$ – arty Oct 14 '13 at 11:47
  • $\begingroup$ I think you may be right that the exact question isn't being answered there. $\endgroup$ – reinierpost Oct 14 '13 at 13:06
9
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Thanks you very much, now when i have this reference i will search for books. can you explain what you mean by "right model for the context sensitive languages" for doing yourself proof? $\endgroup$ – arty Oct 12 '13 at 21:10
  • $\begingroup$ @arty As you know CSL can be defined using context-sensitive grammars or by linear bounded automata. For some tasks the choice of the model is crucial. I like LBA because they are easy to "program". $\endgroup$ – Hendrik Jan Oct 12 '13 at 22:41
  • $\begingroup$ @Jan just wasn't sure what meant by the word "model" - now i understand it is the representation model of the CSL. just to inform you, there is no other place on the web when this information available. I think your input will help a lot of computer science students and postgraduates (like me) who'd like to get some extra knowledge $\endgroup$ – arty Oct 13 '13 at 13:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.