DROPS

Document

DOI: 10.4230/LIPIcs.CONCUR.2026.19

Reaching as Cheap as Possible in 1-Clock Robust Weighted Timed Games

Authors: Nathalie Bertrand, Maëlle Gautrin, and Julie Parreaux

Published in: LIPIcs, Volume 391, 37th International Conference on Concurrency Theory (CONCUR 2026)

Abstract

The value problem for 2-player games on graph generally consists in determining the minimal value Min can ensure against any possible strategy for Max. We consider here the value problem for reachability objectives in weighted timed games (WTGs) under a robust semantics. WTGs are a modelling formalism combining real-time constraints and integer weights on transitions and locations in an adversarial setting. Robustness allows for representing timing imprecisions in the measurement of delays and clock values. Robust weighted timed games have been introduced more than a decade ago: they are undecidable in general, and were quite recently shown decidable for the subclasses of acyclic or divergent robust WTGs. This paper pursues the goal of identifying decidable subclasses and establishes the decidability of the robust value problem for 1-clock WTGs.

Cite as

Nathalie Bertrand, Maëlle Gautrin, and Julie Parreaux. Reaching as Cheap as Possible in 1-Clock Robust Weighted Timed Games. In 37th International Conference on Concurrency Theory (CONCUR 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 391, pp. 19:1-19:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{bertrand_et_al:LIPIcs.CONCUR.2026.19,
  author =	{Bertrand, Nathalie and Gautrin, Ma\"{e}lle and Parreaux, Julie},
  title =	{{Reaching as Cheap as Possible in 1-Clock Robust Weighted Timed Games}},
  booktitle =	{37th International Conference on Concurrency Theory (CONCUR 2026)},
  pages =	{19:1--19:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-447-5},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{391},
  editor =	{Sokolova, Ana and Totzke, Patrick},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CONCUR.2026.19},
  URN =		{urn:nbn:de:0030-drops-273507},
  doi =		{10.4230/LIPIcs.CONCUR.2026.19},
  annote =	{Keywords: timed automata, weighted timed games, robustness, games on graphs}
}

Search Results

Documents authored by Gautrin, Maëlle

Reaching as Cheap as Possible in 1-Clock Robust Weighted Timed Games

Abstract

Cite as

Thanks for your feedback!

Could not send message