文章基本信息

标题：Concurrent Games and Semi-Random Determinacy
本地全文：下载
作者：St{\'e}phane Le Roux
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2018
卷号：117
页码：1-15
DOI：10.4230/LIPIcs.MFCS.2018.40
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：Consider concurrent, infinite duration, two-player win/lose games played on graphs. If the winning condition satisfies some simple requirement, the existence of Player 1 winning (finite-memory) strategies is equivalent to the existence of winning (finite-memory) strategies in finitely many derived one-player games. Several classical winning conditions satisfy this simple requirement. Under an additional requirement on the winning condition, the non-existence of Player 1 winning strategies from all vertices is equivalent to the existence of Player 2 stochastic strategies almost-sure winning from all vertices. Only few classical winning conditions satisfy this additional requirement, but a fairness variant of omega-regular languages does.
关键词：Two-player win/lose; graph; infinite duration; abstract winning condition