Advances in probabilistic model checking with PRISM: variable reordering, quantiles and weak deterministic Büchi automata
Research output: Contribution to journal › Research article › Contributed › peer-review
Contributors
Abstract
The popular model checker PRISM has been successfully used for the modeling and analysis of complex probabilistic systems. As one way to tackle the challenging state explosion problem, PRISM supports symbolic storage and manipulation using multi-terminal binary decision diagrams for representing the models and in the computations. However, it lacks automated heuristics for variable reordering, even though it is well known that the order of BDD variables plays a crucial role for compact representations and efficient computations. In this article, we present a collection of extensions to PRISM. First, we provide support for automatic variable reordering within the symbolic engines of PRISM and allow users to manually control the variable ordering at a fine-grained level. Second, we provide extensions in the realm of reward-bounded properties, namely symbolic computations of quantiles in Markov decision processes and, for both the explicit and symbolic engines, the approximative computation of quantiles for continuous-time Markov chains as well as support for multi-reward-bounded properties. Finally, we provide an implementation for obtaining minimal weak deterministic Büchi automata for the obligation fragment of linear temporal logic (LTL), with applications for expected accumulated reward computations with a finite horizon given by a co-safe LTL formula.
Details
Original language | English |
---|---|
Pages (from-to) | 179-194 |
Number of pages | 16 |
Journal | International Journal on Software Tools for Technology Transfer |
Volume | 20 |
Issue number | 2 (Special issue "TACAS'16") |
Publication status | Published - 2018 |
Peer-reviewed | Yes |
External IDs
researchoutputwizard | legacy.publication#82575 |
---|---|
Scopus | 85018749663 |
ORCID | /0000-0002-5321-9343/work/142236697 |
ORCID | /0000-0003-1724-2586/work/165453586 |
Keywords
Keywords
- Probabilistic model checking, MTBDD, Variable reordering, Quantiles, LTL, Deterministic automata