A Characterization for Decidable Separability by Piecewise Testable Languages

Wojciech Czerwiński, Wim Martens, Lorijn van Rooijen +2

The separability problem for word languages of a class $\mathcal{C}$ by languages of a class $\mathcal{S}$ asks, for two given languages $I$ and $E$ from $\mathcal{C}$, whether the…