---
OA_type: closed access
_id: '3874'
abstract:
- lang: eng
  text: We consider concurrent two-player timed automaton games with omega-regular
    objectives specified as parity conditions. These games offer an appropriate model
    for the synthesis of real-time controllers. Earlier works on timed games focused
    on pure strategies for each player. We study, for the first time, the use of randomized
    strategies in such games. While pure (i.e., nonrandomized) strategies in timed
    games require infinite memory for winning even with respect to reachability objectives,
    we show that randomized strategies can win with finite memory with respect to
    all parity objectives. Also, the synthesized randomized real-time controllers
    are much simpler in structure than the corresponding pure controllers, and therefore
    easier to implement. For safety objectives we prove the existence of pure finite-memory
    winning strategies. Finally, while randomization helps in simplifying the strategies
    required for winning timed parity games, we prove that randomization does not
    help in winning at more states.
acknowledgement: This research was supported in part by the NSF grants CCR-0208875,
  CCR-0225610, CCR-0234690, by the Swiss National Science Foundation, and by the Artist2
  European Network of Excellence.
alternative_title:
- LNCS
article_processing_charge: No
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. Trading infinite memory for uniform
    randomness in timed games. In: <i>11th Workshop on Hybrid Systems: Computation
    and Control</i>. Vol 4981. Springer Nature; 2008:87-100. doi:<a href="https://doi.org/10.1007/978-3-540-78929-1_7">10.1007/978-3-540-78929-1_7</a>'
  apa: 'Chatterjee, K., Henzinger, T. A., &#38; Prabhu, V. (2008). Trading infinite
    memory for uniform randomness in timed games. In <i>11th Workshop on Hybrid Systems:
    Computation and Control</i> (Vol. 4981, pp. 87–100). St. Louis, MO, United States:
    Springer Nature. <a href="https://doi.org/10.1007/978-3-540-78929-1_7">https://doi.org/10.1007/978-3-540-78929-1_7</a>'
  chicago: 'Chatterjee, Krishnendu, Thomas A Henzinger, and Vinayak Prabhu. “Trading
    Infinite Memory for Uniform Randomness in Timed Games.” In <i>11th Workshop on
    Hybrid Systems: Computation and Control</i>, 4981:87–100. Springer Nature, 2008.
    <a href="https://doi.org/10.1007/978-3-540-78929-1_7">https://doi.org/10.1007/978-3-540-78929-1_7</a>.'
  ieee: 'K. Chatterjee, T. A. Henzinger, and V. Prabhu, “Trading infinite memory for
    uniform randomness in timed games,” in <i>11th Workshop on Hybrid Systems: Computation
    and Control</i>, St. Louis, MO, United States, 2008, vol. 4981, pp. 87–100.'
  ista: 'Chatterjee K, Henzinger TA, Prabhu V. 2008. Trading infinite memory for uniform
    randomness in timed games. 11th Workshop on Hybrid Systems: Computation and Control.
    HSCC: Hybrid Systems - Computation and Control, LNCS, vol. 4981, 87–100.'
  mla: 'Chatterjee, Krishnendu, et al. “Trading Infinite Memory for Uniform Randomness
    in Timed Games.” <i>11th Workshop on Hybrid Systems: Computation and Control</i>,
    vol. 4981, Springer Nature, 2008, pp. 87–100, doi:<a href="https://doi.org/10.1007/978-3-540-78929-1_7">10.1007/978-3-540-78929-1_7</a>.'
  short: 'K. Chatterjee, T.A. Henzinger, V. Prabhu, in:, 11th Workshop on Hybrid Systems:
    Computation and Control, Springer Nature, 2008, pp. 87–100.'
conference:
  end_date: 2008-04-24
  location: St. Louis, MO, United States
  name: 'HSCC: Hybrid Systems - Computation and Control'
  start_date: 2008-04-22
date_created: 2018-12-11T12:05:38Z
date_published: 2008-04-03T00:00:00Z
date_updated: 2026-06-10T10:14:59Z
day: '03'
doi: 10.1007/978-3-540-78929-1_7
extern: '1'
intvolume: '      4981'
language:
- iso: eng
month: '04'
oa_version: None
page: 87 - 100
publication: '11th Workshop on Hybrid Systems: Computation and Control'
publication_identifier:
  eissn:
  - 1611-3349
  issn:
  - 0302-9743
publication_status: published
publisher: Springer Nature
publist_id: '2297'
status: public
title: Trading infinite memory for uniform randomness in timed games
type: conference
user_id: 317138e5-6ab7-11ef-aa6d-ffef3953e345
volume: 4981
year: '2008'
...