Graph Games on Ordinals

Julien Cristau & Florian Horn
We consider an extension of Church\'s synthesis problem to ordinals by adding limit transitions to graph games. We consider game arenas where these limit transitions are defined using the sets of cofinal states. In a previous paper, we have shown that such games of ordinal length are determined and that the winner problem is \pspace-complete, for a subclass of arenas where the length of plays is always smaller than $\omega^\omega$. However, the proof uses a...