文章基本信息

标题：Extending Finite-Memory Determinacy by Boolean Combination of Winning Conditions
本地全文：下载
作者：St{\'e}phane Le Roux ; Arno Pauly ; Mickael Randour 等
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2018
卷号：122
页码：1-20
DOI：10.4230/LIPIcs.FSTTCS.2018.38
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：We study finite-memory (FM) determinacy in games on finite graphs, a central question for applications in controller synthesis, as FM strategies correspond to implementable controllers. We establish general conditions under which FM strategies suffice to play optimally, even in a broad multi-objective setting. We show that our framework encompasses important classes of games from the literature, and permits to go further, using a unified approach. While such an approach cannot match ad-hoc proofs with regard to tightness of memory bounds, it has two advantages: first, it gives a widely-applicable criterion for FM determinacy; second, it helps to understand the cornerstones of FM determinacy, which are often hidden but common in proofs for specific (combinations of) winning conditions.
关键词：games on graphs; finite-memory determinacy; multiple objectives