The nondeterministic Mostowski hierarchy and distance-parity automata

Speaker(s)

Christof Loeding (Aachen)

Affiliation

Uniwersytet Warszawski

Date

March 28, 2008, 2:15 p.m.

Room

room 5870

Seminar

Seminar Automata Theory

---

The number of priorities that nondeterministic Mostowski or parity automata on infinite trees can use in their acceptance condition induces a hierarchy of regular tree languages. This talk is about the problem of deciding for a given regular language of infinite trees on which level of the hierarchy it is. I will present a reduction of this problem to the uniform universality problem for distance-parity automata. The latter model is an extension of nested distance desert automata introduced by D. Kirsten in the proof of decidability of the star-height problem for languages of finite words. Distance-parity automata do not simply accept or reject trees but assign to each tree a cost (a natural number or infinity). The uniform universality problem is the question whether the cost function computed by a given distance-parity automaton is bounded by some natural number. It is still open in the general case whether this problem is decidable, but we already know how to solve it for a subclass of distance-parity automata.

---