Simple Priced Timed Games Are Not That Simple

Abstract : Priced timed games are two-player zero-sum games played on priced timed automata (whose locations and transitions are labeled by weights modeling the costs of spending time in a state and executing an action, respectively). The goals of the players are to minimise and maximise the cost to reach a target location, respectively. We consider priced timed games with one clock and arbitrary (positive and negative) 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 reset-acyclic priced timed games (with arbitrary weights and one-clock).
Type de document :
Communication dans un congrès
Prahladh Harsha and G. Ramalingam. Proceedings of the 35th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS'15), Dec 2015, Bangalore, India. Schloss Dagstuhl--Leibniz-Zentrum für Informatik, 45, pp.278-292, Leibniz International Proceedings in Informatics 〈10.4230/LIPIcs.FSTTCS.2015.p〉
Liste complète des métadonnées

Littérature citée [17 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-01452621
Contributeur : Benjamin Monmege <>
Soumis le : jeudi 2 février 2017 - 09:33:28
Dernière modification le : mercredi 14 mars 2018 - 10:36:17
Document(s) archivé(s) le : vendredi 5 mai 2017 - 11:33:45

Fichier

main.pdf
Fichiers produits par l'(les) auteur(s)

Licence


Copyright (Tous droits réservés)

Identifiants

Citation

Thomas Brihaye, Gilles Geeraerts, Axel Haddad, Engel Lefaucheux, Benjamin Monmege. Simple Priced Timed Games Are Not That Simple. Prahladh Harsha and G. Ramalingam. Proceedings of the 35th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS'15), Dec 2015, Bangalore, India. Schloss Dagstuhl--Leibniz-Zentrum für Informatik, 45, pp.278-292, Leibniz International Proceedings in Informatics 〈10.4230/LIPIcs.FSTTCS.2015.p〉. 〈hal-01452621〉

Partager

Métriques

Consultations de la notice

243

Téléchargements de fichiers

24