joint work with Wim Martens, Lorijn van Rooijen, Marc Zeitoun and Georg Zetzsche

I will show that separability of context-free languages by piecewise testable languages is decidable (which is surprising as deciding whether a context-free language is piecewise testable is undecidable). Then I will generalize this result and show a connection between separability by piecewise testable languages, computability of downward closures and diagonal problem.