On the separation property of regular languages

Prelegent(ci)

Henryk Michalewski

Afiliacja

Uniwersytet Warszawski

Termin

2 lutego 2011 14:15

Pokój

p. 5870

Tytuł w języku angielskim

joint result with D. Niwinski).

Seminarium

Seminarium „Teoria automatów”

---

We will show that separation property fails for the regular languages
of index (1,3) on infinite trees. More specifically, we will
construct two disjoint tree languages B_1 and B_2 of index (1,3) not
separable by any set C such that both C and its complement are
recognizable by an automaton of index (1,3).

This theorem extends by one level the previous result obtained jointly
with Sz. Hummel on the inseparability of co-Buchi languages of
infinite trees.

---