Nie jesteś zalogowany |
On the separation property of regular languages
- Prelegent(ci)
- Henryk Michalewski
- Afiliacja
- Uniwersytet Warszawski
- Termin
- 2 lutego 2011 14:15
- Pokój
- p. 5870
- 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.
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.
