9
$\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 ?

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

1 Answer 1

Reset to default
11
$\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.

Improve this answer
$\endgroup$
3
  • $\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, 2013 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, 2013 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, 2013 at 13:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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