Banach-Mazur Games with Simple Winning Strategies

Authors Erich Grädel, Simon Leßenich



PDF
Thumbnail PDF

File

LIPIcs.CSL.2012.305.pdf
  • Filesize: 365 kB
  • 15 pages

Document Identifiers

Author Details

Erich Grädel
Simon Leßenich

Cite AsGet BibTex

Erich Grädel and Simon Leßenich. Banach-Mazur Games with Simple Winning Strategies. In Computer Science Logic (CSL'12) - 26th International Workshop/21st Annual Conference of the EACSL. Leibniz International Proceedings in Informatics (LIPIcs), Volume 16, pp. 305-319, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2012)
https://doi.org/10.4230/LIPIcs.CSL.2012.305

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.
Keywords
  • Banach-Mazur games
  • winning strategies
  • positional determinacy
  • Muller winning conditions

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail