SEPARABILITY PROBLEMS
Wojciech Czerwinski
Two languages K and L are separable by language S if K is included in
S and L has empty intersection with S. For two classes of languages F
and G the F-separability (problem) of G asks whether two given
languages K, L from G are separable by some languages S from the class
F. On the presentation I have shown you how to approach decidability
of PTL-separability of regular languages, where PTL stands for class
of piecewise testable languages. For a project I propose a few
questions and conjectures closely connected with separability problem:
1. For languages L such that it is a context-free language and its
complement is also a context-free language.
Conjecture: whether L is a regular language is decidable.
Another option is to change the class of context-free languages by the
easier class of languages of one counter automata. In that case
problem is simpler, but still showing decidability would be a great
result.
2. For some classes F, G the problem is F-separability of G is
decidable, even quickly, but there are no good bounds for the size of
separator. The task would be to search for such a good bounds.
3. Assume that class G of languages fulfills some reasonable
conditions (G being a full trio).
The conjecture says that then the following two conditions are
equivalent:
- regular-separability of G is decidable
- emptiness of intersection of two languages from G is decidable