The nondeterministic Mostowski hierarchy and distance-parity automata

Prelegent(ci)

Christof Loeding (Aachen)

Afiliacja

Uniwersytet Warszawski

Termin

28 marca 2008 14:15

Pokój

p. 5870

Seminarium

Seminarium „Teoria automatów”

---

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.

---