DI-UMONS : Dépôt institutionnel de l’université de Mons

Recherche transversale
(titres de publication, de périodique et noms de colloque inclus)
2005-09-01 - Article/Dans un journal avec peer-review - Anglais - 15 page(s)

Brihaye Thomas , Bruyère Véronique , Raskin Jean-François, "On optimal timed strategies" in Lecture Notes in Computer Science, 3829, 49-64

  • Edition : Springer, Berlin (Germany)
  • Codes CREF : Théorie des graphes (DI1146), Informatique mathématique (DI1160)
  • Unités de recherche UMONS : Mathématiques effectives (S820), Informatique théorique (S829)
Texte intégral :

Abstract(s) :

(Anglais) In this paper, we study timed games played on weighted timed automata. In this context, the reachability problem asks if, given a set T of locations and a cost C, Player 1 has a strategy to force the game into T with a cost less than C no matter how Player 2 behaves. Recently, this problem has been studied independently by Alur et al and by Bouyer et al. In those two works, a semi-algorithm is proposed to solve the reachability problem, which is proved to terminate under a condition imposing the non-zenoness of cost. In this paper, we show that in the general case the existence of a strategy for Player 1 to win the game with a bounded cost is undecidable. Our undecidability result holds for weighted timed game automata with five clocks. On the positive side, we show that if we restrict the number of clocks to one and we limit the form of the cost on locations, then the semi-algorithm proposed by Bouyer et al always terminates.

Identifiants :
  • DOI : 10.1007/11603009_5