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/
Grädel, Erich ;
Leßenich, Simon
Banach-Mazur Games with Simple Winning Strategies
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 |