文章基本信息

标题：Parity and Streett Games with Costs
本地全文：下载
作者：Nathanaël Fijalkow ; Martin Zimmermann
期刊名称：Logical Methods in Computer Science
印刷版ISSN：1860-5974
电子版ISSN：1860-5974
出版年度：2014
卷号：10
期号：2
页码：1
DOI：10.2168/LMCS-10(2:14)2014
出版社：Technical University of Braunschweig
摘要：We consider two-player games played on finite graphs equipped with costs on edges and introduce two winning conditions, cost-parity and cost-Streett, which require bounds on the cost between requests and their responses. Both conditions generalize the corresponding classical omega-regular conditions and the corresponding finitary conditions. For parity games with costs we show that the first player has positional winning strategies and that determining the winner lies in NP and coNP. For Streett games with costs we show that the first player has finite-state winning strategies and that determining the winner is EXPTIME-complete. The second player might need infinite memory in both games. Both types of games with costs can be solved by solving linearly many instances of their classical variants.
其他关键词：Parity Games, Streett Games, Costs, Half-positional Determinacy