Parameter synthesis for probabilistic timed automata using stochastic game abstractions

Journal article

We propose a symbolic method to synthesise optimal values of timing parameters for probabilistic timed automata, in the sense that the probability of reaching some set of states is either maximised or minimised. Our first algorithm, based on forward exploration of the symbolic states, can only guarantee parameter values that correspond to upper (resp. lower) bounds on maximum (resp. minimum) reachability probability. To ensure precise reachability probabilities, we adapt the game-based abstraction refinement method. In the parametric setting, our method is able to determine all the possible maximum or minimum reachability probabilities that arise for different values of timing parameters, and yields optimal valuations represented as a set of symbolic constraints between parameters. We report on a prototype implementation of the algorithm in the Prism model checker and its evaluation on a case study.

Authors: Jovanović, A; Kwiatkowska, M

• Publication status: Published
• Peer review status: Peer reviewed
• Publisher: Elsevier
• Journal: Theoretical Computer Science
• Volume: 735
• Pages: 64-81
• Publication date: 2017-05-11
• Acceptance date: 2017-05-05
• DOI: 10.1016/j.tcs.2017.05.005
• ISSN: 0304-3975
• Keywords: parameter synthesis; stochastic games; Markov decision processes; probabilistic timed automata; probabilistic reachability; model checking