License: Creative Commons Attribution-NonCommercial-NoDerivs 3.0 Unported license (CC BY-NC-ND 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.FSTTCS.2008.1748
URN: urn:nbn:de:0030-drops-17485
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2008/1748/
Go to the corresponding LIPIcs Volume Portal

Cristau, Julien ; Horn, Florian

Graph Games on Ordinals

pdf-format:
08004.CristauJulien.1768.pdf (0.4 MB)

Abstract

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.

BibTeX - Entry

@InProceedings{cristau_et_al:LIPIcs:2008:1748,
  author =	{Julien Cristau and Florian Horn},
  title =	{{Graph Games on Ordinals}},
  booktitle =	{IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science},
  pages =	{143--154},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-08-8},
  ISSN =	{1868-8969},
  year =	{2008},
  volume =	{2},
  editor =	{Ramesh Hariharan and Madhavan Mukund and V Vinay},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2008/1748},
  URN =		{urn:nbn:de:0030-drops-17485},
  doi =		{10.4230/LIPIcs.FSTTCS.2008.1748},
  annote =	{Keywords: Games, ordinals, zeno}
}

Keywords: Games, ordinals, zeno
Collection: IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science
Issue Date: 2008
Date of publication: 05.12.2008

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI