文章基本信息

标题：Banach-Mazur Games with Simple Winning Strategies
本地全文：下载
作者：Erich Gr{\"a}del ; Simon Le{\ss}enich
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2012
卷号：16
页码：305-319
DOI：10.4230/LIPIcs.CSL.2012.305
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：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.
关键词：Banach-Mazur games; winning strategies; positional determinacy; Muller winning conditions