Nie jesteś zalogowany |
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
- 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.
