snippetModerate
How to prove that context sensitive languages are closed under intersection and complement?
Viewed 0 times
languagesareintersectionclosedandproveunderthatcomplementhow
Problem
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 ?
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 ?
Solution
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.
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.
Context
StackExchange Computer Science Q#15014, answer score: 11
Revisions (0)
No revisions yet.