The Value Problem for Weighted Timed Games with Two Clocks is Undecidable
Fuente:
arXiv
Guardado en:
| Autores principales: | , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2025
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866918304104316928 |
|---|---|
| author | Guilmant, Quentin Ouaknine, Joël Vialard, Isa |
| author_facet | Guilmant, Quentin Ouaknine, Joël Vialard, Isa |
| contents | The Value Problem for weighted timed games (WTGs) consists in determining, given a two-player weighted timed game with a reachability objective and a rational threshold, whether or not the value of the game exceeds the threshold. This problem was shown to be undecidable some ten years ago for WTGs making use of at least three clocks, and is known to be decidable for single-clock WTGs. In this paper, we establish undecidability for two-clock WTGs making use of non-negative weights, even in a time-bounded setting, closing the last remaining major gap in our algorithmic understanding of WTGs. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2507_10550 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | The Value Problem for Weighted Timed Games with Two Clocks is Undecidable Guilmant, Quentin Ouaknine, Joël Vialard, Isa Computer Science and Game Theory The Value Problem for weighted timed games (WTGs) consists in determining, given a two-player weighted timed game with a reachability objective and a rational threshold, whether or not the value of the game exceeds the threshold. This problem was shown to be undecidable some ten years ago for WTGs making use of at least three clocks, and is known to be decidable for single-clock WTGs. In this paper, we establish undecidability for two-clock WTGs making use of non-negative weights, even in a time-bounded setting, closing the last remaining major gap in our algorithmic understanding of WTGs. |
| title | The Value Problem for Weighted Timed Games with Two Clocks is Undecidable |
| topic | Computer Science and Game Theory |
| url | https://arxiv.org/abs/2507.10550 |