*banner
 

Minimum-time reachability in timed games
Thomas Brihaye, Tom Henzinger, Vinayak Prabhu, Jean-François Raskin

Citation
Thomas Brihaye, Tom Henzinger, Vinayak Prabhu, Jean-François Raskin. "Minimum-time reachability in timed games". ICALP 2007 Automata, Languages and Programming, 825-837, July, 2007.

Abstract
We consider the minimum-time reachability problem in concurrent two-player timed automaton game structures. We show how to compute the minimum time needed by a player to reach a target location against all possible choices of the opponent.We do not put any syntactic restriction on the game structure, nor do we require any player to guarantee time divergence.We only require players to use receptive strategies which do not block time. The minimal time is computed in part using a fixpoint expression, which we show can be evaluated on equivalence classes of a non-trivial extension of the clock-region equivalence relation for timed automata.

Electronic downloads

Citation formats  
  • HTML
    Thomas Brihaye, Tom Henzinger, Vinayak Prabhu,
    Jean-François Raskin. <a
    href="http://chess.eecs.berkeley.edu/pubs/250.html"
    >Minimum-time reachability in timed games</a>,
    ICALP 2007 Automata, Languages and Programming, 825-837,
    July, 2007.
  • Plain text
    Thomas Brihaye, Tom Henzinger, Vinayak Prabhu,
    Jean-François Raskin. "Minimum-time
    reachability in timed games". ICALP 2007 Automata,
    Languages and Programming, 825-837, July, 2007.
  • BibTeX
    @inproceedings{BrihayeHenzingerPrabhuRaskin07_MinimumtimeReachabilityInTimedGames,
        author = {Thomas Brihaye and Tom Henzinger and Vinayak
                  Prabhu and Jean-François Raskin},
        title = {Minimum-time reachability in timed games},
        booktitle = {ICALP 2007 Automata, Languages and Programming},
        pages = {825-837},
        month = {July},
        year = {2007},
        abstract = {We consider the minimum-time reachability problem
                  in concurrent two-player timed automaton game
                  structures. We show how to compute the minimum
                  time needed by a player to reach a target location
                  against all possible choices of the opponent.We do
                  not put any syntactic restriction on the game
                  structure, nor do we require any player to
                  guarantee time divergence.We only require players
                  to use receptive strategies which do not block
                  time. The minimal time is computed in part using a
                  fixpoint expression, which we show can be
                  evaluated on equivalence classes of a non-trivial
                  extension of the clock-region equivalence relation
                  for timed automata. },
        URL = {http://chess.eecs.berkeley.edu/pubs/250.html}
    }
    

Posted by Vinayak Prabhu on 14 May 2007.
Groups: chess
For additional information, see the Publications FAQ or contact webmaster at chess eecs berkeley edu.

Notice: This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright.

©2002-2018 Chess