Separability of Regular Languages by Piecewise Testable Languages

Prelegent(ci)

Wojciech Czerwiński

Afiliacja

University of Bayreuth

Termin

6 marca 2013 14:15

Pokój

p. 5870

Tytuł w języku angielskim

joint work with Wim Martens and Tomas Masopust

Seminarium

Seminarium „Teoria automatów”

---

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).

---