Regular Separability and Intersection Emptiness are Independent Problems

Abstract

The problem of \emph{regular separability} asks, given two languages $K$ and $L$, whether there exists a regular language $S$ with $K\subseteq S$ and $S\cap L=\varnothing$. This problem has recently been studied for various classes of languages. All the results on regular separability obtained so far exhibited a noteworthy correspondence with the intersection emptiness problem: In eachcase, regular separability is decidable if and only if intersection emptiness is decidable. This raises the question whether under mild assumptions, regular separability can be reduced to intersection emptiness and vice-versa. We present counterexamples showing that none of the two problems can be reduced to the other. More specifically, we describe language classes ${\mathcal{C}}_1$, ${\mathcal{D}}_1$, ${\mathcal{C}}_2$, ${\mathcal{D}}_2$ such that (i)~intersection emptiness is decidable for ${\mathcal{C}}_1$ and ${\mathcal{D}}_1$, but regular separability is undecidable for ${\mathcal{C}}_1$ and ${\mathcal{D}}_1$ and (ii)~regular separability is decidable for ${\mathcal{C}}_2$ and ${\mathcal{D}}_2$, but intersection emptiness is undecidable for ${\mathcal{C}}_2$ and ${\mathcal{D}}_2$.