Simple strategies for Banach-Mazur games and fairly correct systems

Thomas Brihaye
(University of Mons)
Quentin Menet
(University of Mons)

In 2006, Varacca and Völzer proved that on finite graphs, omega-regular large sets coincide with omega-regular sets of probability 1, by using the existence of positional strategies in the related Banach-Mazur games. Motivated by this result, we try to understand relations between sets of probability 1 and various notions of simple strategies (including those introduced in a recent paper of Grädel and Lessenich). Then, we introduce a generalisation of the classical Banach-Mazur game and in particular, a probabilistic version whose goal is to characterise sets of probability 1 (as classical Banach-Mazur games characterise large sets). We obtain a determinacy result for these games, when the winning set is a countable intersection of open sets.

In Gabriele Puppis and Tiziano Villa: Proceedings Fourth International Symposium on Games, Automata, Logics and Formal Verification (GandALF 2013), Borca di Cadore, Dolomites, Italy, 29-31th August 2013, Electronic Proceedings in Theoretical Computer Science 119, pp. 21–34.
Published: 16th July 2013.

ArXived at: https://dx.doi.org/10.4204/EPTCS.119.5 bibtex PDF
References in reconstructed bibtex, XML and HTML format (approximated).
Comments and questions to: eptcs@eptcs.org
For website issues: webmaster@eptcs.org