joint work with Wim Martens and Tomas Masopust

Speaker(s)

Wojciech Czerwiński

Affiliation

University of Bayreuth

Date

March 6, 2013, 2:15 p.m.

Room

room 5870

Title in Polish

Separability of Regular Languages by Piecewise Testable Languages

Seminar

Seminar Automata Theory

---

The separation problem is formulated as follows: given two regular languages K and L, does there exists a "simple" regular language S separating them, i.e. including all words from K and no words from L? I will give our motivation to study this problem coming from the XML Schemas and show how to solve it in polynomial time (for family of simple languages equal piecewise testable languages).

---