Separating regular languages by piecewise testable and unambiguous languages
Thomas Place, Lorijn van Rooijen, Marc Zeitoun · arXiv (Cornell University) · 2013
Separation is a classical problem asking whether, given two sets belonging to some class, it is possible to separate them by a set from a smaller class. We discuss the separation problem for regular languages. We give a Ptime algorithm to check whether two given regular languages are separable by a piecewise testable language, that is, whether a $BΣ1(