2026-07-21T21:12:27Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:3680 2024-03-06T10:34:22Z ddc:004 open_access

Banach-Mazur Games with Simple Winning Strategies Grädel, Erich Leßenich, Simon Banach-Mazur games winning strategies positional determinacy Muller winning conditions 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Erich Grädel and Simon Leßenich 2012 Is Part Of LIPIcs, Volume 16, Computer Science Logic (CSL'12) - 26th International Workshop/21st Annual Conference of the EACSL (2012) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.CSL.2012.305 urn:nbn:de:0030-drops-36806 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CSL.2012.305 eng https://creativecommons.org/licenses/by-nc-nd/3.0/legalcode