Fijalkow, Nathanaël and Zimmermann, Martin - Parity and Streett Games with Costs

lmcs:794 - Logical Methods in Computer Science, June 26, 2014, Volume 10, Issue 2
Parity and Streett Games with Costs

Authors: Fijalkow, Nathanaël and Zimmermann, Martin

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.


Source : oai:arXiv.org:1207.0663
DOI : 10.2168/LMCS-10(2:14)2014
Volume: Volume 10, Issue 2
Published on: June 26, 2014
Submitted on: June 25, 2015
Keywords: Computer Science - Logic in Computer Science,Computer Science - Computational Complexity,Computer Science - Computer Science and Game Theory


Share

Browsing statistics

This page has been seen 18 times.
This article's PDF has been downloaded 5 times.