3
$\begingroup$

This is a follow-up to this question, which asks for an example of a non-regular language $L$ which satisfies the following condition, intersection resilience:

If $L'$ is context-free then so is $L \cap L'$.

We know that all regular languages are intersection-resilient, and clearly every intersection-resilient language is context-free. Ginsburg and Spanier showed in 1964, in their paper Bounded ALGOL-like languages, that every context-free subset of $x^*y^*$ is intersection-resilient (Theorem 6.1, Corollary 2).

Which languages are intersection-resilient?

$\endgroup$
  • 1
    $\begingroup$ A related question is whether it is decidable whether a given context-free language is intersection-resilient. Another related question is whether the intersection of an intersection-resilient language and an context-free language is intersection-resilient. Note that the intersection of two intersection-resilient languages is intersection-resilient. $\endgroup$ – Apass.Jack May 29 at 15:44
1
$\begingroup$

Just a few notes (I'll try to add the proofs later).

Intersection-resilience seems closed under homomorphism.

A necessary condition for intersection-resilience is that for all homomorphisms $\varphi : \Sigma \to \Sigma \cup\ \{\epsilon \}$; $\varphi(L) \cap x^*y^*x^*$ must be a regular language (where $x$ and $y$ are any two distinct symbols of $\Sigma$).

So the result of Ginsburg and Spanier seems "tight" (if we use the same homomorphism trick).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.