Classes containing boolean closure of CFLs

Question

So I asked a similar question on MathOverflow, 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?

Answer 1

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's work on conjunctive and boolean grammars, but I don't recall any pumping results.