---
OA_place: repository
OA_type: green
_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
article_processing_charge: No
arxiv: 1
author:
- first_name: Krishnendu
  full_name: Chatterjee, Krishnendu
  id: 2E5DCA20-F248-11E8-B48F-1D18A9856A87
  last_name: Chatterjee
  orcid: 0000-0002-4561-241X
- first_name: Thomas A
  full_name: Henzinger, Thomas A
  id: 40876CD8-F248-11E8-B48F-1D18A9856A87
  last_name: Henzinger
  orcid: 0000−0002−2985−7724
- first_name: Vinayak
  full_name: Prabhu, Vinayak
  last_name: Prabhu
citation:
  ama: 'Chatterjee K, Henzinger TA, Prabhu V. Timed parity games: complexity and robustness.
    In: <i>Proceedings of the 6th International Conference on Formal Modeling and
    Analysis of Timed Systems</i>. Vol 5215. Springer Nature; 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. In <i>Proceedings of the 6th international conference
    on Formal Modeling and Analysis of Timed Systems</i> (Vol. 5215, pp. 124–140).
    Saint Malo, France: Springer Nature. <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.” In <i>Proceedings of the 6th International
    Conference on Formal Modeling and Analysis of Timed Systems</i>, 5215:124–40.
    Springer Nature, 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,” in <i>Proceedings of the 6th international conference on Formal
    Modeling and Analysis of Timed Systems</i>, Saint Malo, France, 2008, vol. 5215,
    pp. 124–140.'
  ista: 'Chatterjee K, Henzinger TA, Prabhu V. 2008. Timed parity games: complexity
    and robustness. Proceedings of the 6th international conference on Formal Modeling
    and Analysis of Timed Systems. FORMATS: Formal Modeling and Analysis of Timed
    Systems, LNCS, vol. 5215, 124–140.'
  mla: 'Chatterjee, Krishnendu, et al. “Timed Parity Games: Complexity and Robustness.”
    <i>Proceedings of the 6th International Conference on Formal Modeling and Analysis
    of Timed Systems</i>, vol. 5215, Springer Nature, 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:, Proceedings of the 6th International
    Conference on Formal Modeling and Analysis of Timed Systems, Springer Nature,
    2008, pp. 124–140.
conference:
  end_date: 2008-09-17
  location: Saint Malo, France
  name: 'FORMATS: Formal Modeling and Analysis of Timed Systems'
  start_date: 2008-09-15
date_created: 2018-12-11T12:05:39Z
date_published: 2008-10-01T00:00:00Z
date_updated: 2026-07-06T13:25:38Z
day: '01'
doi: 10.1007/978-3-540-85778-5_10
extern: '1'
external_id:
  arxiv:
  - '0807.1165'
intvolume: '      5215'
language:
- iso: eng
month: '10'
oa_version: None
page: 124 - 140
publication: Proceedings of the 6th international conference on Formal Modeling and
  Analysis of Timed Systems
publication_identifier:
  eissn:
  - 1611-3349
  isbn:
  - '9783540857778'
  issn:
  - 0302-9743
publication_status: published
publisher: Springer Nature
publist_id: '2294'
related_material:
  record:
  - id: '3315'
    relation: later_version
    status: public
status: public
title: 'Timed parity games: complexity and robustness'
type: conference
user_id: 317138e5-6ab7-11ef-aa6d-ffef3953e345
volume: 5215
year: '2008'
...