joint work with Andre Arnold and Henryk Michalewski

Speaker(s)

Damian Niwiński

Affiliation

Uniwersytet Warszawski

Date

Oct. 5, 2011, 2:15 p.m.

Room

room 5870

Title in Polish

On separation question for tree languages

Seminar

Seminar Automata Theory

---

Once we know that a class C is different from co-C,
we may ask a more subtle question: can any two disjoint
sets in C be ``approximated'' by their super-sets in
co-C, still disjoint ?

In the classical hierarchies, typically one of two
dual classes on each level enjoys such property. We pursue the
question for the Rabin-Mostowski index hierarchy of alternating
automata on infinite trees.  We discover that the property
fails for all Sigma classes, which extends our previous
result obtained with Szczepan Hummel concerning the
co-Buchi sets. It is open whether the property holds
for Pi classes for levels > 2. The result for trees
builds on an analogous result for the index hierarchy
of deterministic automata on infinite words. In this case
we solve the problem completely: the approximation (separation)
property holds for Pi classes and fails for Sigma classes.
As a by-product we discover a simplification of the Arnold's
proof of the strictness of the Rabin-Mostowski index hierarchy.
More specifically: the use of the Banach Fixed-Point Theorem
can be replaced by an explicit construction of a fixed point.

---