License
when quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.CSL.2012.305
URN: urn:nbn:de:0030-drops-36806
URL: http://drops.dagstuhl.de/opus/volltexte/2012/3680/

Grädel, Erich ; Leßenich, Simon

Banach-Mazur Games with Simple Winning Strategies

pdf-format:
Dokument 1.pdf (365 KB)


Abstract

We discuss several notions of "simple" winning strategies for Banach-Mazur games on graphs, such as positional strategies, move-counting or length-counting strategies, and strategies with a memory based on finite appearance records (FAR). We investigate classes of Banach-Mazur games that are determined via these kinds of winning strategies. Banach-Mazur games admit stronger determinacy results than classical graph games. For instance, all Banach-Mazur games with omega-regular winning conditions are positionally determined. Beyond the omega-regular winning conditions, we focus here on Muller conditions with infinitely many colours. We investigate the infinitary Muller conditions that guarantee positional determinacy for Banach-Mazur games. Further, we determine classes of such conditions that require infinite memory but guarantee determinacy via move-counting strategies, length-counting strategies, and FAR-strategies. We also discuss the relationships between these different notions of determinacy.

BibTeX - Entry

@InProceedings{grdel_et_al:LIPIcs:2012:3680,
  author =	{Erich Gr{\"a}del and Simon Le{\ss}enich},
  title =	{{Banach-Mazur Games with Simple Winning Strategies}},
  booktitle =	{Computer Science Logic (CSL'12) - 26th International Workshop/21st Annual Conference of the EACSL},
  pages =	{305--319},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-42-2},
  ISSN =	{1868-8969},
  year =	{2012},
  volume =	{16},
  editor =	{Patrick C{\'e}gielski and Arnaud Durand},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2012/3680},
  URN =		{urn:nbn:de:0030-drops-36806},
  doi =		{http://dx.doi.org/10.4230/LIPIcs.CSL.2012.305},
  annote =	{Keywords: Banach-Mazur games, winning strategies, positional determinacy, Muller winning conditions}
}

Keywords: Banach-Mazur games, winning strategies, positional determinacy, Muller winning conditions
Seminar: Computer Science Logic (CSL'12) - 26th International Workshop/21st Annual Conference of the EACSL
Issue date: 2012
Date of publication: 27.08.2012


DROPS-Home | Fulltext Search | Imprint Published by LZI