2026-07-20T11:02:23Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:6879 2024-03-06T10:39:06Z ddc:004 open_access

Mean-Payoff Games on Timed Automata Guha, Shibashis Jurdzinski, Marcin Krishna, Shankara Narayanan Trivedi, Ashutosh Timed Automata Mean-Payoff Games Controller-Synthesis Mean-payoff games on timed automata are played on the infinite weighted graph of configurations of priced timed automata between two players - Player Min and Player Max - by moving a token along the states of the graph to form an infinite run. The goal of Player Min is to minimize the limit average weight of the run, while the goal of the Player Max is the opposite. Brenguier, Cassez, and Raskin recently studied a variation of these games and showed that mean-payoff games are undecidable for timed automata with five or more clocks. We refine this result by proving the undecidability of mean-payoff games with three clocks. On a positive side, we show the decidability of mean-payoff games on one-clock timed automata with binary price-rates. A key contribution of this paper is the application of dynamic programming based proof techniques applied in the context of average reward optimization on an uncountable state and action space. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Shibashis Guha and Marcin Jurdzinski and Shankara Narayanan Krishna and Ashutosh Trivedi 2016 Is Part Of LIPIcs, Volume 65, 36th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2016) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.FSTTCS.2016.44 urn:nbn:de:0030-drops-68797 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2016.44 eng https://creativecommons.org/licenses/by/3.0/legalcode