The Separation ProblemDr. Pascal Weil, CNRS and Universite de Bordeaux, France, will give a series of lectures on the Separation Problem. Lecture schedule
Abstract The separation problem for a class V of (regular) languages is a generalization of the membership problem. In the latter problem, one asks whether a given language L is in class V. In the separation problem, given two disjoint languages K and L, one asks whether there exists a third language M in V, containing K and avoiding L. Finding a (minimal) separator is an interesting additional problem. If V is a 'simple' class that is well understood, the separation problem for V gives new information on languages that are not in V, something that the membership problem cannot provide. Another point of view on the separation problem is that of an over- (for K) or under- (for the complement of L) approximation of arbitrary languages by a language in V, which can be useful in various verification settings. A third motivation is more technical but no less important: the membership problem is not very ‘resilient’. Typically, the membership decision problem for complex (composed) classes cannot be reduced to the corresponding problem for smaller classes. The separation problem seems to have much better properties in this respect. The separation problem has been proved to be decidable for a good number of classical families of regular languages, especially among those defined by fragments of FO[<]. It has also been used to get the recent advances in the long-standing open problem of the decidability of the quantifier alternation hierarchy within FO[<]. This series of talks will give an introduction to the separation problem, from its language-theoretic definition above, to algebraic, topological and combinatorial equivalent points of view. We will also give its algorithmic solution for some interesting classes of languages. If time permits, we will briefly describe more recent advances on the topic. |
