| ||||
| ||||
![]() Title:A journey through negatively-weighted timed games: undecidability, decidability, approximability Authors:Benjamin Monmege Conference:MoRe 2018 Tags:game theory, quantitative games and synthesis Abstract: Weighted timed games are zero-sum games played by two players on a timed automaton equipped with weights, where one player wants to minimise the accumulated weight while reaching a target. Used in a reactive synthesis perspective, this quantitative extension of timed games allows one to measure the quality of controllers in real-time systems. Weighted timed games are notoriously difficult and quickly undecidable, even when restricted to non-negative weights. However, for a few years now, we explored, and we continue to explore, the world of weighted timed games with negative weights too, in order to get a more useful modelling mechanism. This gave rise to stronger undecidability results, but we also discovered new decidable fragments. In this talk, I will survey these results: decidability when limiting the number of distinct weights in the game, using corner-point abstraction techniques; decidability for a large fragment of one-clock weighted timed games, and for the so-called divergent weighted timed games, using value iteration schemes; approximability in the case of the so-called almost-divergent weighted timed games. A journey through negatively-weighted timed games: undecidability, decidability, approximability ![]() A journey through negatively-weighted timed games: undecidability, decidability, approximability | ||||
Copyright © 2002 – 2025 EasyChair |