2026-07-23T08:35:16Z https://drops.dagstuhl.de/oai

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

1½-Player Stochastic StopWatch Games Roychowdhury, Sparsa Timed Automata Stopwatches Stochastic Timed Games Stochastic timed games (STGs), introduced by Bouyer and Forejt, generalize continuous-time Markov chains and timed automata. Depending on the number of players - 2, 1, or 0 - subclasses of stochastic timed games are classified as 2½-player, 1½-player, and ½-player games where the ½ symbolizes the presence of the stochastic player. The qualitative and quantitative reachability problem for STGs was studied in [Patricia Bouyer and Vojtech Forejt, 2009] and [S. Akshay et al., 2016]. In this paper, we introduce stochastic stopwatch games (SSG), an extension of (STG) from clocks to stopwatches. We focus on 1½-player SSGs and prove that with two variables which can be either a clock or a stopwatch, qualitative reachability is decidable, whereas, if we increase the number of variables to three, with at least one stopwatch, the problem becomes undecidable. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Sparsa Roychowdhury 2021 Is Part Of LIPIcs, Volume 206, 28th International Symposium on Temporal Representation and Reasoning (TIME 2021) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.TIME.2021.17 urn:nbn:de:0030-drops-147934 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.TIME.2021.17 eng https://creativecommons.org/licenses/by/4.0/legalcode