Consider two context-free languages $L\_1, L\_2$. Of course, $L\_1 - L\_2, L\_1\cap L\_2, \bar{L}\_1$, etc. are not necessarily context-free, but they are context-sensitive (the second is easy, the other two I think follow from Immerman-Szelepcsenyi (if I spelled that right)). However, there's no nice structure to context-sensitive languages (e.g., pumping/Ogden's lemmas), so I was wondering if the inclusion is any better--is the 'closure' of CFLs under the standard operations (well, only $\cap$ and complementation) a proper subset of CSLs, and if so, does it have any natural description?


Thanks much.



'Closure' of CFLs under complementation and intersection
Grammars involving the usual context-free operations plus intersection are called [conjunctive grammars](https://en.wikipedia.org/wiki/Conjunctive_grammar). Adding negation (in addition to intersection) gives [boolean grammars](https://en.wikipedia.org/wiki/Boolean_grammar).


[Alexander Okhotin](http://users.utu.fi/aleokh/) ([Wayback Machine](https://web.archive.org/web/20210416115256/http://users.utu.fi/aleokh/)) has done quite a bit of recent work on the closure properties of the languages (sets of strings) specified by these sorts of grammars. He also has a paper showing how to parse these languages using a variant on the Lang-Tomita GLR algorithm.


As you note, CFLs are strictly included in conjunctive grammars. Surprisingly, it appears that the strictness of the inclusion relationship between conjunctive and boolean grammars is still an [open problem (#6)](http://users.utu.fi/aleokh/boolean/update_mar2010.pdf) ([Wayback Machine](https://web.archive.org/web/20210506212640/http://users.utu.fi/aleokh/boolean/update_mar2010.pdf)). The last inclusion is also strict: there are context-sensitive languages which cannot be specified by a boolean grammar.


