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

Parity and Streett Games with Costs

Science & Mathematics Published 2012 Verification Pending

Overview & Synopsis

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.

Indexed from repository: HAL Open Science (hal.science)
Loading document from verified source...
Keyboard Shortcuts: ← / → for pages • + / - for zoom • 0 to fit width Powered by Mozilla PDF.js v3.11

Document Information

Document Title Parity and Streett Games with Costs
Author / Organization Nathanaël Fijalkow, Martin Zimmermann
Subject & Discipline Multidisciplinary Academic Open Research
Categories Science & Mathematics
Publication Year 2012
License / Rights Open Access / Creative Commons
Resource Verification Listed PDF (Verification Pending)
Original Host Website HAL Open Science (hal.science)
File Format application/pdf (Portable Document Format)
Language EN
Catalog ID DOC-250846
Original Source Link Visit Source Page on hal.science »