Two remarks on the role of ranks in parity games

Speaker(s)

Damian Niwiński

Affiliation

Uniwersytet Warszawski

Date

April 3, 2007, 2:15 p.m.

Room

room 5870

Seminar

Seminar Automata Theory

---

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.

---