Nie jesteś zalogowany |
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.
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.
