---
_id: '3876'
abstract:
- lang: eng
  text: We consider two-player games played in real time on game structures with clocks
    and parity objectives. 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 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., nonconcurrent) finite-state (i.e., untimed) parity games. The
    states of the resulting game are pairs of clock regions of the original game.
    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. 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 strategies. Using a limit-robust 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. We show that exact strategies
    are more powerful than limit-robust strategies, which are more powerful than bounded-robust
    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.
acknowledgement: This research was supported in part by the NSF grants CCR-0132780,
  CNS-0720884, and CCR-0225610, and by the European COMBEST project.
alternative_title:
- LNCS
author:
- first_name: Krishnendu
  full_name: Krishnendu Chatterjee
  id: 2E5DCA20-F248-11E8-B48F-1D18A9856A87
  last_name: Chatterjee
  orcid: 0000-0002-4561-241X
- first_name: Thomas A
  full_name: Thomas Henzinger
  id: 40876CD8-F248-11E8-B48F-1D18A9856A87
  last_name: Henzinger
  orcid: 0000−0002−2985−7724
- first_name: Vinayak
  full_name: Prabhu, Vinayak S
  last_name: Prabhu
citation:
  ama: 'Chatterjee K, Henzinger TA, Prabhu V. Timed parity games: complexity and robustness.
    In: Vol 5215. Springer; 2008:124-140. doi:<a href="https://doi.org/10.1007/978-3-540-85778-5_10">10.1007/978-3-540-85778-5_10</a>'
  apa: 'Chatterjee, K., Henzinger, T. A., &#38; Prabhu, V. (2008). Timed parity games:
    complexity and robustness (Vol. 5215, pp. 124–140). Presented at the FORMATS:
    Formal Modeling and Analysis of Timed Systems, Springer. <a href="https://doi.org/10.1007/978-3-540-85778-5_10">https://doi.org/10.1007/978-3-540-85778-5_10</a>'
  chicago: 'Chatterjee, Krishnendu, Thomas A Henzinger, and Vinayak Prabhu. “Timed
    Parity Games: Complexity and Robustness,” 5215:124–40. Springer, 2008. <a href="https://doi.org/10.1007/978-3-540-85778-5_10">https://doi.org/10.1007/978-3-540-85778-5_10</a>.'
  ieee: 'K. Chatterjee, T. A. Henzinger, and V. Prabhu, “Timed parity games: complexity
    and robustness,” presented at the FORMATS: Formal Modeling and Analysis of Timed
    Systems, 2008, vol. 5215, pp. 124–140.'
  ista: 'Chatterjee K, Henzinger TA, Prabhu V. 2008. Timed parity games: complexity
    and robustness. FORMATS: Formal Modeling and Analysis of Timed Systems, LNCS,
    vol. 5215, 124–140.'
  mla: 'Chatterjee, Krishnendu, et al. <i>Timed Parity Games: Complexity and Robustness</i>.
    Vol. 5215, Springer, 2008, pp. 124–40, doi:<a href="https://doi.org/10.1007/978-3-540-85778-5_10">10.1007/978-3-540-85778-5_10</a>.'
  short: K. Chatterjee, T.A. Henzinger, V. Prabhu, in:, Springer, 2008, pp. 124–140.
conference:
  name: 'FORMATS: Formal Modeling and Analysis of Timed Systems'
date_created: 2018-12-11T12:05:39Z
date_published: 2008-10-01T00:00:00Z
date_updated: 2025-04-14T12:58:09Z
day: '01'
doi: 10.1007/978-3-540-85778-5_10
extern: 1
intvolume: '      5215'
month: '10'
page: 124 - 140
publication_status: published
publisher: Springer
publist_id: '2294'
quality_controlled: 0
related_material:
  record:
  - id: '3315'
    relation: later_version
    status: public
status: public
title: 'Timed parity games: complexity and robustness'
type: conference
volume: 5215
year: '2008'
...