Regular Separability and Intersection Emptiness are Independent Problems

Speaker(s)

Ramanathan S. Thinniyam

Affiliation

Max Planck Institute for Software Systems (MPI-SWS)

Date

Nov. 20, 2019, 2:15 p.m.

Room

room 5050

Seminar

Seminar Automata Theory

---

The problem of regular separability asks, given two languages $K$ and $L$, whether there exists a regular language $S$ with $K \subseteq S$ and $S \cap L = \emptyset$. This problem becomes interesting when the input languages $K$ and $L$ are drawn from language classes beyond the regular languages. For such classes, a mild and useful assumption is that they are full trios, i.e. closed under rational transductions. All the results on regular separability for full trios obtained so far exhibited a noteworthy correspondence with the intersection emptiness problem: In each case, regular separability is decidable if and only if intersection emptiness is decidable. This raises the question whether for full trios, regular separability can be reduced to intersection emptiness or vice-versa.

We present counterexamples showing that neither of the two problems can be reduced to the other. More specifically, we describe full trios C1, D1, C2, D2 such that (i) intersection emptiness is decidable for C1 and D1, but regular separability is undecidable for C1 and D1 and (ii) regular separability is decidable for C2 and D2, but intersection emptiness is undecidable for C2 and D2. 

This is joint work with Georg Zetzsche.

---