Separability of context-free languages by piecewise testable languages

Prelegent(ci)

Wojciech Czerwiński

Afiliacja

Uniwersytet Warszawski

Termin

6 kwietnia 2016 14:15

Pokój

p. 5870

Tytuł w języku angielskim

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

Seminarium

Seminarium „Teoria automatów”

---

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.

---