'Closure' of CFLs under complementation and intersection 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.
 A: Grammars involving the usual context-free operations plus intersection are called conjunctive grammars.  Adding negation (in addition to intersection) gives boolean grammars.
Alexander Okhotin (Wayback Machine) 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) (Wayback Machine).  The last inclusion is also strict: there are context-sensitive languages which cannot be specified by a boolean grammar.
A: Would An infinite hierarchy of intersections of context-free languages (Liu Weiner 1973) answer your question?  They prove that the intersection of $k$ CFL forms a class strictly contained in the intersection of $k +1$ CFL.
A: This looks interesting as well.
Kutrib, Martin; Malcher, Andreas; Wotschke, Detlef, The Boolean closure of linear context-free languages, Calude, Cristian S. (ed.) et al., Developments in language theory. 8th international conference, DLT 2004, Auckland, New Zealand, December 13–17, 2004. Proceedings. Berlin: Springer (ISBN 3-540-24014-4/pbk). Lecture Notes in Computer Science 3340, 284-295 (2004). ZBL1117.68408, MR2152151.
