Separation theorems in the Wagner hierarchy of rational omega-langauges

Prelegent(ci)

Andre Arnold

Afiliacja

Labri, Bordeaux

Termin

8 czerwca 2011 14:15

Pokój

p. 5870

Seminarium

Seminarium „Teoria automatów”

---

In the Borel hierarchy every pair of disjoint
Pi_n sets is separable by a Delta_n set, and
there are pairs of disjoint Sigma_n sets which
are not separable.

It is still a partially open question whether
these separation results hold for the Mostowski
hierarchy, i.e.,  for sets of trees defined by
parity automata.

A first milestone on the road to the solution
of this separation problem is to solve it for the
Wagner hierarchy of languages defined by
deterministic parity word automata.

---