The separation problem for regular languages by piecewise testable languages
Lorijn van Rooijen, Marc Zeitoun · arXiv (Cornell University) · 2013
Separation is a classical problem in mathematics and computer science. It asks whether, given two sets belonging to some class, it is possible to separate them by another set of a smaller class. We present and discuss the separation problem for regular languages. We then give a direct polynomial time algorithm to check whether two given regular languages are separable by a piecewise testable language, that is, whether a $BΣ1(