<p>This is not an answer to your question per se, but might explain why finding sensible classes of languages more or less fitting your requirements will be hard: recall that the emptiness of intersection of two context-free languages is undecidable, thus the full boolean closure of CFLs is not a very interesting class... (In fact, any R.E. language $L$ can be expressed as $h(L_1\cap L_2)$ for $L_1$ and $L_2$ deterministic context-free and $h$ an homomorphism.)</p>

<p>More in the scope of your question, you can look at <a href="http://users.utu.fi/aleokh/" rel="nofollow">Alexander Okhotin</a>'s work on conjunctive and boolean grammars, but I don't recall any pumping results.</p>

CC BY-SA 2.5
2011-01-11T17:45:18.327Z
You're right--good point. I don't think Okhotin's boolean grammars have any pumping-type results, so ah well! I'll wait a bit more to see if anyone comes along with any magic, but I've taken a different route in my attack anyway.
alpoge
CC BY-SA 4.0
2022-08-12T12:48:27.333Z
The link to Alexander Okhotin doesn't work now - the new website seems to be here: https://users.math-cs.spbu.ru/~okhotin/
Martin
CC BY-SA 2.5
2011-01-11T12:12:04.213Z
2011-01-11T12:12:04.213Z
Sylvain
<p>So I asked a similar question on <a href="https://mathoverflow.net/questions/51657/closure-of-cfls-under-complementation-and-intersection">MathOverflow</a>, but I now realize I asked the wrong question and asked it in the wrong place.</p>

<p>Anyway, I'm searching for a class of languages containing the boolean closure of CFLs that has a 'pumping-type' condition on it. What I've found so far are:</p>

<ul>
<li>MCFGs (multiple context-free languages), which have a nice pumping lemma and contain CFLs (though it's not obvious if they contain the boolean closure of CFLs, since they're not boolean-closed themselves), 
<li>ET0L languages (which contain CFLs, have a 'pumping-type' lemma, and are (full) AFLs themselves--but I don't think they necessarily contain the boolean closure of CFLs), 
<li>Mildly CSLs (which apparently have pumping-type lemmas?), 
<li>Indexed languages (which have a 'shrinking' lemma), etc.
</ul>

<p>Now, I'm certainly no specialist in formal language theory, so I don't know too much about these classes. Anyway, does such a class exist, and, if so, where can I find papers/etc. on it?</p>

<reference-request><fl.formal-languages><context-free>
Classes containing boolean closure of CFLs
alpoge
# Classes containing boolean closure of CFLs

(Asked by: username_0 on 2011-01-11)

So I asked a similar question on [MathOverflow](https://mathoverflow.net/questions/51657/closure-of-cfls-under-complementation-and-intersection), but I now realize I asked the wrong question and asked it in the wrong place.

Anyway, I'm searching for a class of languages containing the boolean closure of CFLs that has a 'pumping-type' condition on it. What I've found so far are:

* MCFGs (multiple context-free languages), which have a nice pumping lemma and contain CFLs (though it's not obvious if they contain the boolean closure of CFLs, since they're not boolean-closed themselves),* ET0L languages (which contain CFLs, have a 'pumping-type' lemma, and are (full) AFLs themselves--but I don't think they necessarily contain the boolean closure of CFLs),* Mildly CSLs (which apparently have pumping-type lemmas?),* Indexed languages (which have a 'shrinking' lemma), etc.

Now, I'm certainly no specialist in formal language theory, so I don't know too much about these classes. Anyway, does such a class exist, and, if so, where can I find papers/etc. on it?

**Tags:** reference-request, fl.formal-languages, context-free

---

## 1 answers

### Answer by username_1 on 2011-01-11. Score: 5 | Accepted answer

This is not an answer to your question per se, but might explain why finding sensible classes of languages more or less fitting your requirements will be hard: recall that the emptiness of intersection of two context-free languages is undecidable, thus the full boolean closure of CFLs is not a very interesting class... (In fact, any R.E. language $L$ can be expressed as $h(L\_1\cap L\_2)$ for $L\_1$ and $L\_2$ deterministic context-free and $h$ an homomorphism.)

More in the scope of your question, you can look at [Alexander Okhotin](http://users.utu.fi/aleokh/)'s work on conjunctive and boolean grammars, but I don't recall any pumping results.

> **Comments:**
> **username_0**: You're right--good point. I don't think Okhotin's boolean grammars have any pumping-type results, so ah well! I'll wait a bit more to see if anyone comes along with any magic, but I've taken a different route in my attack anyway.  
> **username_2**: The link to Alexander Okhotin doesn't work now - the new website seems to be here: https://users.math-cs.spbu.ru/~okhotin/  

---

