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

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

Bouyer Patricia, Brihaye Thomas , Bruyère Véronique , Raskin Jean-François, "On the optimal reachability problem of weighted timed automata" in Formal Methods in System Design, 31, Issue 2, 135-175

  • Edition : Springer Science & Business Media B.V.
  • Codes CREF : Informatique mathématique (DI1160)
  • Unités de recherche UMONS : Mathématiques effectives (S820), Informatique théorique (S829)
Texte intégral :

Abstract(s) :

(Anglais) We study the cost-optimal reachability problem for weighted timed automata such that positive and negative costs are allowed on edges and locations. By optimality, we mean an infimum cost as well as a supremum cost. We show that this problem is PSpace-Complete. Our proof uses techniques of linear programming, and thus exploits an important property of optimal runs: their time-transitions use a time t which is arbitrarily close to an integer. We then propose an extension of the region graph, the weighted discrete graph, whose structure gives light on the way to solve the cost-optimal reachability problem. We also give an application of the cost-optimal reachability problem in the context of timed games.

Identifiants :
  • DOI : 10.1007/s10703-007-0035-4