joint result with D. Niwinski).

Speaker(s)

Henryk Michalewski

Affiliation

Uniwersytet Warszawski

Date

Feb. 2, 2011, 2:15 p.m.

Room

room 5870

Title in Polish

On the separation property of regular languages

Seminar

Seminar Automata Theory

---

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.

---