joint work with Wim Martens and Tomas Masopust

The separation problem is formulated as follows: given two regular languages K and L, does there exists a "simple" regular language S separating them, i.e. including all words from K and no words from L? I will give our motivation to study this problem coming from the XML Schemas and show how to solve it in polynomial time (for family of simple languages equal piecewise testable languages).