Regular Separability and Intersection Emptiness are Independent Problems
share
The problem of regular separability asks, given two languages K and L, whether there exists a regular language S with K⊆ S and S∩ L=∅. 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 C_1, D_1, C_2, D_2 such that (i) intersection emptiness is decidable for C_1 and D_1, but regular separability is undecidable for C_1 and D_1 and (ii) regular separability is decidable for C_2 and D_2, but intersection emptiness is undecidable for C_2 and D_2.
READ FULL TEXT