On separation question for tree languages

Prelegent(ci)

Damian Niwiński

Afiliacja

Uniwersytet Warszawski

Termin

5 października 2011 14:15

Pokój

p. 5870

Tytuł w języku angielskim

joint work with Andre Arnold and Henryk Michalewski

Seminarium

Seminarium „Teoria automatów”

---

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.

---