You are not logged in |
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.
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.
