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.CSL.2012.305
URN: urn:nbn:de:0030-drops-36806
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2012/3680/
Go to the corresponding LIPIcs Volume Portal

Grädel, Erich ; Leßenich, Simon

Banach-Mazur Games with Simple Winning Strategies

pdf-format:
26.pdf (0.4 MB)

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 =		{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
Collection: Computer Science Logic (CSL'12) - 26th International Workshop/21st Annual Conference of the EACSL
Issue Date: 2012
Date of publication: 03.09.2012

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