Timed parity games: Complexity and robustness Journal Article

Author(s): Chatterjee, Krishnendu; Henzinger, Thomas A; Prabhu, Vinayak
Article Title: Timed parity games: Complexity and robustness
Affiliation IST Austria
Abstract: We consider two-player games played in real time on game structures with clocks where the objectives of players are described using parity conditions. The games are concurrent in that at each turn, both players independently propose a time delay and an action, and the action with the shorter delay is chosen. To prevent a player from winning by blocking time, we restrict each player to play strategies that ensure that the player cannot be responsible for causing a zeno run. First, we present an efficient reduction of these games to turn-based (i.e., not concurrent) finite-state (i.e., untimed) parity games. Our reduction improves the best known complexity for solving timed parity games. Moreover, the rich class of algorithms for classical parity games can now be applied to timed parity games. The states of the resulting game are based on clock regions of the original game, and the state space of the finite game is linear in the size of the region graph. Second, we consider two restricted classes of strategies for the player that represents the controller in a real-time synthesis problem, namely, limit-robust and bounded-robust winning strategies. Using a limit-robust winning strategy, the controller cannot choose an exact real-valued time delay but must allow for some nonzero jitter in each of its actions. If there is a given lower bound on the jitter, then the strategy is bounded-robust winning. We show that exact strategies are more powerful than limit-robust strategies, which are more powerful than bounded-robust winning strategies for any bound. For both kinds of robust strategies, we present efficient reductions to standard timed automaton games. These reductions provide algorithms for the synthesis of robust real-time controllers.
Journal Title: Logical Methods in Computer Science
Volume: 7
Issue 4:8
ISSN: 1860-5974
Publisher: International Federation of Computational Logic  
Date Published: 2011-12-14
Start Page: 1
End Page: 55
Copyright Statement: CC BY-ND 2.0
Sponsor: This research was supported in part by the NSF grants CCR-013 2780, CNS-0720884, and CCR-0225610, and by the European COMBEST project.
DOI: 10.2168/LMCS-7(4:8)2011
Open access: yes (repository)
IST Austria Authors
  1. Thomas A. Henzinger
    415 Henzinger
Related IST Austria Work