One-Clock Priced Timed Games with Arbitrary Weights - MOVE Modélisation et Vérification - LIS Laboratoire d'Informatique et Systèmes de Marseille (UMR 7020) Accéder directement au contenu
Pré-Publication, Document De Travail Année : 2019

One-Clock Priced Timed Games with Arbitrary Weights

Résumé

Priced timed games are two-player zero-sum games played on priced timed au-tomata (whose locations and transitions are labeled by weights modeling the price of spending time in a state and executing an action, respectively). The goals of the players are to minimise and maximise the price to reach a target location, respectively. We consider priced timed games with one clock and arbitrary integer weights and show that, for an important subclass of theirs (the so-called simple priced timed games), one can compute, in exponential time, the optimal values that the players can achieve, with their associated optimal strategies. As side results, we also show that one-clock priced timed games are determined and that we can use our result on simple priced timed games to solve the more general class of so-called negative-reset-acyclic priced timed games (with arbitrary integer weights and one clock). The decidability status of the full class of priced timed games with one-clock and arbitrary integer weights still remains open.
Fichier principal
Vignette du fichier
main.pdf (590.19 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

hal-02424743 , version 1 (28-12-2019)
hal-02424743 , version 2 (27-09-2022)

Identifiants

  • HAL Id : hal-02424743 , version 1

Citer

Thomas Brihaye, Gilles Geeraerts, Axel Haddad, Engel Lefaucheux, Benjamin Monmege. One-Clock Priced Timed Games with Arbitrary Weights. 2019. ⟨hal-02424743v1⟩
177 Consultations
68 Téléchargements

Partager

Gmail Facebook X LinkedIn More