Nie jesteś zalogowany | Zaloguj się

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