2026-07-20T09:01:37Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:20799 2024-08-29T05:40:58Z ddc:004 open_access

Inaproximability in Weighted Timed Games Guilmant, Quentin Ouaknine, Joël Weighted timed games approximation undecidability We consider two-player, turn-based weighted timed games played on timed automata equipped with (positive and negative) integer weights, in which one player seeks to reach a goal location whilst minimising the cumulative weight of the underlying path. Although the value problem for such games (is the value of the game below a given threshold?) is known to be undecidable, the question of whether one can approximate this value has remained a longstanding open problem. In this paper, we resolve this question by showing that approximating arbitrarily closely the value of a given weighted timed game is computationally unsolvable. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Quentin Guilmant and Joël Ouaknine 2024 Is Part Of LIPIcs, Volume 311, 35th International Conference on Concurrency Theory (CONCUR 2024) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.CONCUR.2024.27 urn:nbn:de:0030-drops-207998 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CONCUR.2024.27 eng https://creativecommons.org/licenses/by/4.0/legalcode