Separation property for wB and wS-regular languages

Speaker(s)

Michał Skrzypczak

Affiliation

Uniwersytet Warszawski

Date

Nov. 23, 2011, 2:15 p.m.

Room

room 5870

Seminar

Seminar Automata Theory

---

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.

---