Cost-parity and cost-Streett games



Fijalkow, N and Zimmermann, M ORCID: 0000-0002-8038-2453
(2012) Cost-parity and cost-Streett games. .

[img] Text
fijz.pdf - OA Published Version

Download (531kB) | Preview

Abstract

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 ω-regular conditions as well as the corresponding finitary conditions. For cost-parity games we show that the first player has positional winning strategies and that determining the winner lies in NP ∩ coNP. For cost-Streett games we show that the first player has finite-state winning strategies and that determining the winner is EXPTIME-complete. This unifies the complexity results for the classical and finitary variants of these games. Both types of cost games can be solved by solving linearly many instances of their classical variants. © N. Fijalkow and M. Zimmermann.

Item Type: Conference or Workshop Item (Unspecified)
Depositing User: Symplectic Admin
Date Deposited: 15 Jul 2019 12:57
Last Modified: 02 Aug 2021 07:19
DOI: 10.4230/LIPIcs.FSTTCS.2012.124
URI: https://livrepository.liverpool.ac.uk/id/eprint/3049680