# '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.

-
The title makes this sort of look like a question about introductory CS... By 'closure' I mean the smallest set containing the set of CFLs that is closed under those operations. –  alpoge Jan 10 '11 at 16:39

Grammars involving the usual context-free operations plus intersection are called conjunctive grammars. Adding negation (in addition to intersection) gives boolean grammars.

Alexander Okhotin 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). The last inclusion is also strict: there are context-sensitive languages which cannot be specified by a boolean grammar.

-
This looks right. Thanks! –  alpoge Jan 10 '11 at 18:35
It seems conjunctive grammars also strictly contain the set of $2$-intersection languages with complementation (or whatever one might call them), since in the unary case the set of conjunctive languages contains nonregular languages (which are obviously not in the previous set). Though conjunctive/boolean grammars do indeed answer the question. Thanks again! –  alpoge Jan 10 '11 at 19:28
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.
Hm. I suppose that probably shows that the 'closure' I'm talking about is pretty complicated at least. What I really want to know is about $2$-intersection languages--well, specifically, $2$-intersection languages 'adjoined' with the co-CFL languages, so to speak. –  alpoge Jan 10 '11 at 16:29