---
_id: '4630'
abstract:
- lang: eng
  text: We consider concurrent two-person games played in real time, in which the
    players decide both which action to play, and when to play it. Such timed games
    differ from untimed games in two essential ways. First, players can take each
    other by surprise, because actions are played with delays that cannot be anticipated
    by the opponent. Second, a player should not be able to win the game by preventing
    time from diverging. We present a model of timed games that preserves the element
    of surprise and accounts for time divergence in a way that treats both players
    symmetrically and applies to all ω-regular winning conditions. We prove that the
    ability to take each other by surprise adds extra power to the players. For the
    case that the games are specified in the style of timed automata, we provide symbolic
    algorithms for their solution with respect to all ω-regular winning conditions.
    We also show that for these timed games, memory strategies are more powerful than
    memoryless strategies already in the case of reachability objectives.
acknowledgement: Supported in part by the AFOSR MURI grant F49620-00-1-0327, the DARPA
  grant F33615-C-98-3614, the MARCO grant 98-DT-660, -the ONR grant N00014-02-1-0671,
  the NSF grants CCR-9988172, CCR-0225610, and CCR-0234690, the NSF CAREER award CCR-0132780,
  and the MIUR grant MEFISTO.
alternative_title:
- LNCS
article_processing_charge: No
author:
- first_name: Luca
  full_name: De Alfaro, Luca
  last_name: De Alfaro
- first_name: Marco
  full_name: Faella, Marco
  last_name: Faella
- 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: Ritankar
  full_name: Majumdar, Ritankar
  last_name: Majumdar
- first_name: Mariëlle
  full_name: Stoelinga, Mariëlle
  last_name: Stoelinga
citation:
  ama: 'De Alfaro L, Faella M, Henzinger TA, Majumdar R, Stoelinga M. The element
    of surprise in timed games. In: <i>Proceedings of the 14th International Conference
    on Concurrency Theory</i>. Vol 2761. Schloss Dagstuhl - Leibniz-Zentrum für Informatik;
    2003:144-158. doi:<a href="https://doi.org/10.1007/978-3-540-45187-7_9">10.1007/978-3-540-45187-7_9</a>'
  apa: 'De Alfaro, L., Faella, M., Henzinger, T. A., Majumdar, R., &#38; Stoelinga,
    M. (2003). The element of surprise in timed games. In <i>Proceedings of the 14th
    International Conference on Concurrency Theory</i> (Vol. 2761, pp. 144–158). Marseille,
    France: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. <a href="https://doi.org/10.1007/978-3-540-45187-7_9">https://doi.org/10.1007/978-3-540-45187-7_9</a>'
  chicago: De Alfaro, Luca, Marco Faella, Thomas A Henzinger, Ritankar Majumdar, and
    Mariëlle Stoelinga. “The Element of Surprise in Timed Games.” In <i>Proceedings
    of the 14th International Conference on Concurrency Theory</i>, 2761:144–58. Schloss
    Dagstuhl - Leibniz-Zentrum für Informatik, 2003. <a href="https://doi.org/10.1007/978-3-540-45187-7_9">https://doi.org/10.1007/978-3-540-45187-7_9</a>.
  ieee: L. De Alfaro, M. Faella, T. A. Henzinger, R. Majumdar, and M. Stoelinga, “The
    element of surprise in timed games,” in <i>Proceedings of the 14th International
    Conference on Concurrency Theory</i>, Marseille, France, 2003, vol. 2761, pp.
    144–158.
  ista: 'De Alfaro L, Faella M, Henzinger TA, Majumdar R, Stoelinga M. 2003. The element
    of surprise in timed games. Proceedings of the 14th International Conference on
    Concurrency Theory. CONCUR: Concurrency Theory, LNCS, vol. 2761, 144–158.'
  mla: De Alfaro, Luca, et al. “The Element of Surprise in Timed Games.” <i>Proceedings
    of the 14th International Conference on Concurrency Theory</i>, vol. 2761, Schloss
    Dagstuhl - Leibniz-Zentrum für Informatik, 2003, pp. 144–58, doi:<a href="https://doi.org/10.1007/978-3-540-45187-7_9">10.1007/978-3-540-45187-7_9</a>.
  short: L. De Alfaro, M. Faella, T.A. Henzinger, R. Majumdar, M. Stoelinga, in:,
    Proceedings of the 14th International Conference on Concurrency Theory, Schloss
    Dagstuhl - Leibniz-Zentrum für Informatik, 2003, pp. 144–158.
conference:
  end_date: 2003-09-05
  location: Marseille, France
  name: 'CONCUR: Concurrency Theory'
  start_date: 2003-09-03
date_created: 2018-12-11T12:09:51Z
date_published: 2003-08-21T00:00:00Z
date_updated: 2024-01-08T10:05:30Z
day: '21'
doi: 10.1007/978-3-540-45187-7_9
extern: '1'
intvolume: '      2761'
language:
- iso: eng
month: '08'
oa_version: None
page: 144 - 158
publication: Proceedings of the 14th International Conference on Concurrency Theory
publication_identifier:
  isbn:
  - '9783540407539'
publication_status: published
publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik
publist_id: '78'
quality_controlled: '1'
scopus_import: '1'
status: public
title: The element of surprise in timed games
type: conference
user_id: ea97e931-d5af-11eb-85d4-e6957dddbf17
volume: 2761
year: '2003'
...