Citation
Luca de Alfaro, Marco Faella, Tom Henzinger, Rupak Majumdar. "The Element of Surprise in Timed Games". CONCUR 2003 - Concurrency Theory, 144-158, 2003.

Abstract
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 omega-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 omega-regular winning conditions. We also show that for these timed games, memory strategies are more powerful than memorylless strategies already in the case of reachability objectives.

Electronic downloads

• http://dx.doi.org/10.1007/978-3-540-45187-7_9

• HTML

  Luca de Alfaro, Marco Faella, Tom Henzinger, Rupak Majumdar.
  <a
  href="http://chess.eecs.berkeley.edu/pubs/731.html"
  >The Element of Surprise in Timed Games</a>, CONCUR
  2003 - Concurrency Theory, 144-158, 2003.

• Plain text

  Luca de Alfaro, Marco Faella, Tom Henzinger, Rupak Majumdar.
  "The Element of Surprise in Timed Games". CONCUR
  2003 - Concurrency Theory, 144-158, 2003.

• BibTeX

  @inproceedings{deAlfaroFaellaHenzingerMajumdar03_ElementOfSurpriseInTimedGames,
      author = {Luca de Alfaro and Marco Faella and Tom Henzinger
                and Rupak Majumdar},
      title = {The Element of Surprise in Timed Games},
      booktitle = {CONCUR 2003 - Concurrency Theory},
      pages = {144-158},
      year = {2003},
      abstract = {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 omega-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 omega-regular
                winning conditions. We also show that for these
                timed games, memory strategies are more powerful
                than memorylless strategies already in the case of
                reachability objectives.},
      URL = {http://chess.eecs.berkeley.edu/pubs/731.html}
  }
  

Posted by Christopher Brooks on 4 Nov 2010.
For additional information, see the Publications FAQ or contact webmaster at chess eecs berkeley edu.