Finding Provably Optimal Markov Chains
Open Access
- 20 March 2021
- book chapter
- Published by Springer Nature
- Vol. 12651, 173-190
Abstract
Parametric Markov chains (pMCs) are Markov chains with symbolic (aka: parametric) transition probabilities. They are a convenient operational model to treat robustness against uncertainties. A typical objective is to find the parameter values that maximize the reachability of some target states. In this paper, we consider automatically proving robustness, that is, an $$\varepsilon $$ -close upper bound on the maximal reachability probability. The result of our procedure actually provides an almost-optimal parameter valuation along with this upper bound.We propose to tackle these ETR-hard problems by a tight combination of two significantly different techniques: monotonicity checking and parameter lifting. The former builds a partial order on states to check whether a pMC is (local or global) monotonic in a certain parameter, whereas parameter lifting is an abstraction technique based on the iterative evaluation of pMCs without parameter dependencies. We explain our novel algorithmic approach and experimentally show that we significantly improve the time to determine almost-optimal synthesis.
Keywords
This publication has 21 references indexed in Scilit:
- Verification and control of partially observable probabilistic systemsReal-Time Systems, 2017
- Parameter Synthesis for Markov Models: Faster Than Ever2016
- The Probabilistic Model Checking Landscape2016
- Precise parameter synthesis for stochastic biochemical systemsActa Informatica, 2016
- A Greedy Approach for the Efficient Repair of Stochastic Models2015
- Model Repair for Markov Decision Processes2013
- Synthesis for PCTL in Parametric Markov Decision Processes2011
- Attaining Monotonicity for Bayesian Networks2011
- Probabilistic reachability for parametric Markov modelsInternational Journal on Software Tools for Technology Transfer, 2010
- Parametric probabilistic transition systems for system design and analysisFormal Aspects of Computing, 2007