2026-07-22T02:00:28Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:1748 2024-03-06T10:33:05Z ddc:004 open_access

Graph Games on Ordinals Cristau, Julien Horn, Florian Games ordinals zeno 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Julien Cristau and Florian Horn 2008 Is Part Of LIPIcs, Volume 2, IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (2008) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.FSTTCS.2008.1748 urn:nbn:de:0030-drops-17485 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2008.1748 eng https://creativecommons.org/licenses/by-nc-nd/3.0/legalcode