License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.TIME.2021.17
URN: urn:nbn:de:0030-drops-147934
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2021/14793/
Go to the corresponding LIPIcs Volume Portal

Roychowdhury, Sparsa

1½-Player Stochastic StopWatch Games

pdf-format:
LIPIcs-TIME-2021-17.pdf (0.8 MB)

Abstract

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.

BibTeX - Entry

@InProceedings{roychowdhury:LIPIcs.TIME.2021.17,
  author =	{Roychowdhury, Sparsa},
  title =	{{1½-Player Stochastic StopWatch Games}},
  booktitle =	{28th International Symposium on Temporal Representation and Reasoning (TIME 2021)},
  pages =	{17:1--17:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-206-8},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{206},
  editor =	{Combi, Carlo and Eder, Johann and Reynolds, Mark},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2021/14793},
  URN =		{urn:nbn:de:0030-drops-147934},
  doi =		{10.4230/LIPIcs.TIME.2021.17},
  annote =	{Keywords: Timed Automata, Stopwatches, Stochastic Timed Games}
}

Keywords: Timed Automata, Stopwatches, Stochastic Timed Games
Collection: 28th International Symposium on Temporal Representation and Reasoning (TIME 2021)
Issue Date: 2021
Date of publication: 16.09.2021

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI