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

Speaker(s)

Wojciech Czerwiński

Affiliation

Uniwersytet Warszawski

Date

April 6, 2016, 2:15 p.m.

Room

room 5870

Title in Polish

Separability of context-free languages by piecewise testable languages

Seminar

Seminar Automata Theory

---

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.

---