10.4230/LIPICS.FSTTCS.2008.1748
Cristau, Julien
Julien
Cristau
Horn, Florian
Florian
Horn
Graph Games on Ordinals
Schloss Dagstuhl – Leibniz-Zentrum für Informatik
2008
Article
Games
ordinals
zeno
Hariharan, Ramesh
Ramesh
Hariharan
Mukund, Madhavan
Madhavan
Mukund
Vinay, V
V
Vinay
2008
2008-12-05
2008-12-05
2008-12-05
en
urn:nbn:de:0030-drops-17485
10.4230/LIPIcs.FSTTCS.2008
978-3-939897-08-8
1868-8969
10.4230/LIPIcs.FSTTCS.2008
LIPIcs, Volume 2, FSTTCS 2008
IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science
2013
2
20
143
154
Schloss Dagstuhl – Leibniz-Zentrum für Informatik
Hariharan, Ramesh
Ramesh
Hariharan
Mukund, Madhavan
Madhavan
Mukund
Vinay, V
V
Vinay
1868-8969
Leibniz International Proceedings in Informatics (LIPIcs)
2008
2
Schloss Dagstuhl – Leibniz-Zentrum für Informatik
12 pages
432825 bytes
application/pdf
Creative Commons Attribution-NonCommercial-NoDerivs 3.0 Unported license
info:eu-repo/semantics/openAccess
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 rather involved reduction to classical Muller games, and the
resulting strategies need infinite memory.
We adapt the LAR reduction to prove the determinacy in the general case, and
to generate strategies with finite memory, using a reduction to games where
the limit transitions are defined by priorities. We provide an algorithm for
computing the winning regions of both players in these games, with a
complexity similar to parity games. Its analysis yields three results:
determinacy without hypothesis on the length of the plays, existence of
memoryless strategies, and membership of the winner problem in \npconp.
LIPIcs, Vol. 2, IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, pages 143-154