Separation theorems in the Wagner hierarchy of rational omega-langauges

Speaker(s)

Andre Arnold

Affiliation

Labri, Bordeaux

Date

June 8, 2011, 2:15 p.m.

Room

room 5870

Seminar

Seminar Automata Theory

---

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.

---