Thomas Brihaye ; Gilles Geeraerts ; Axel Haddad ; Engel Lefaucheux ; Benjamin Monmege - One-Clock Priced Timed Games with Negative Weights

lmcs:6764 - Logical Methods in Computer Science, August 9, 2022, Volume 18, Issue 3 - https://doi.org/10.46298/lmcs-18(3:17)2022
One-Clock Priced Timed Games with Negative WeightsArticle

Authors: Thomas Brihaye ; Gilles Geeraerts ; Axel Haddad ; Engel Lefaucheux ; Benjamin Monmege

    Priced timed games are two-player zero-sum games played on priced timed automata (whose locations and transitions are labeled by weights modelling the cost 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 integer weights and show that, for an important subclass of them (the so-called simple priced timed games), one can compute, in pseudo-polynomial 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.


    Volume: Volume 18, Issue 3
    Published on: August 9, 2022
    Accepted on: June 18, 2022
    Submitted on: September 8, 2020
    Keywords: Computer Science - Computer Science and Game Theory,Computer Science - Logic in Computer Science
    Funding:
      Source : OpenAIRE Graph
    • Collective Adaptive System SynThesIs with Non-zero-sum Games; Funder: European Commission; Code: 601148
    • Efficient Techniques and Tools for Verification and Synthesis of Real-Time Systems; Funder: French National Research Agency (ANR); Code: ANR-18-CE40-0015
    • Challenges for Logic, Transducers and Automata; Funder: French National Research Agency (ANR); Code: ANR-16-CE40-0007

    Consultation statistics

    This page has been seen 1973 times.
    This article's PDF has been downloaded 494 times.