Two remarks on the role of ranks in parity games

Prelegent(ci)

Damian Niwiński

Afiliacja

Uniwersytet Warszawski

Termin

3 kwietnia 2007 14:15

Pokój

p. 5870

Seminarium

Seminarium „Teoria automatów”

---

These observations are of very different nature, but they can be read as evidences for the lower bound, and the upper bound, respectively. At first we show that the number of ranks gives rise to a strict hierarchy of the parity-game tree languages, in the sense of Wadge reducibility. Next, we observe that the algorithm for solving parity game need not always depend exponentially on the number of ranks.

---