Speaker |
Martin Zimmermann |
Title | Cost-Parity and Cost-Street Games |
When | 28.11.2012, 10.00 |
Where | Room 5052 |
Abstract | Cost-parity and cost-Streett games are played in weighted arenas and extend classical and finitary parity and Streett games by requiring bounds on the cost between requests and their responses. For cost-parity games we show that the first player has positional winning strategies and that determining the winner lies in NP and co-NP. 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.
Joint work with Nathanaël Fijalkow (LIAFA & University of Warsaw) |
Slides |
Event calendar
- Subscribe to the ics feed.
Upcoming Events
- No Events