Separation property for wB and wS-regular languages

Prelegent(ci)

Michał Skrzypczak

Afiliacja

Uniwersytet Warszawski

Termin

23 listopada 2011 14:15

Pokój

p. 5870

Seminarium

Seminarium „Teoria automatów”

---

In this paper we show that wB and wS-regular languages satisfy the following separation-type theorem:

Given two disjoint languages both recognised by wB (resp. wS)-automata, there exists an w-regular language separating them.

In particular if a language and its complement are wB (resp. wS)-regular then the language is w-regular.

The result is especially interesting because wB-regular languages are complements of wS-regular languages (see [BC06]). Therefore, the above theorem shows that these are two mutually dual classes that both have the separation property.

The proof technique is quite simple. It makes noticeable use of the framework for the analysis of wB and wS-regular languages proposed by Szymon Toruńczyk in his PhD thesis.

---