Stochastic timed games revisited

DOI10.4230/LIPICS.MFCS.2016.8zbMATH Open1398.91054arXiv1607.05671OpenAlexW2963821209MaRDI QIDQ4608565FDOQ4608565

Authors: S. Akshay, Patricia Bouyer, Shankara Narayanan Krishna, Lakshmi Manasa, Ashutosh Trivedi 

Publication date: 21 March 2018

Abstract: Stochastic timed games (STGs), introduced by Bouyer and Forejt, naturally generalize both continuous-time Markov chains and timed automata by providing a partition of the locations between those controlled by two players (Player Box and Player Diamond) with competing objectives and those governed by stochastic laws. Depending on the number of players---$2$, $1$, or $0$---subclasses of stochastic timed games are often classified as $2frac12$-player, $1frac12$-player, and $frac12$-player games where the $frac12$ symbolizes the presence of the stochastic "nature" player. For STGs with reachability objectives it is known that $1frac12$-player one-clock STGs are decidable for qualitative objectives, and that $2frac12$-player three-clock STGs are undecidable for quantitative reachability objectives. This paper further refines the gap in this decidability spectrum. We show that quantitative reachability objectives are already undecidable for $1frac12$ player four-clock STGs, and even under the time-bounded restriction for $2frac12$-player five-clock STGs. We also obtain a class of $1frac12$, $2frac12$ player STGs for which the quantitative reachability problem is decidable.

Full work available at URL: https://arxiv.org/abs/1607.05671

Recommendations

• Reachability in Stochastic Timed Games
• Stochastic Real-Time Games with Qualitative Timed Automata Objectives
• Continuous-time stochastic games with time-bounded reachability
• Reachability-Time Games on Timed Automata
• Expected reachability-time games

zbMATH Keywords

stochastic gamestimed automatatwo-counter machines

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Stochastic games, stochastic differential games (91A15) Games of timing (91A55)

Cited In (11)

• Stochastic scheduling games with Markov decision arrival processes
• Cost vs. Time in Stochastic Games and Markov Automata
• Expected reachability-time games
• Probabilistic timed automata with clock-dependent probabilities
• On timed alternating simulation for concurrent timed games
• 1½-Player Stochastic StopWatch Games
• Efficient On-the-Fly Algorithms for Partially Observable Timed Games
• Title not available (Why is that?)
• Stochastic Real-Time Games with Qualitative Timed Automata Objectives
• Reachability in Stochastic Timed Games
• Probabilistic timed automata with one clock and initialised clock-dependent probabilities

This page was built for publication: Stochastic timed games revisited

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4608565)