Advances in probabilistic model checking with PRISM: variable reordering, quantiles and weak deterministic Büchi automata

Publikation: Beitrag in FachzeitschriftForschungsartikelBeigetragenBegutachtung

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

OriginalspracheEnglisch
Seiten (von - bis)179-194
Seitenumfang16
FachzeitschriftInternational Journal on Software Tools for Technology Transfer
Jahrgang20
Ausgabenummer2 (Special issue "TACAS'16")
PublikationsstatusVeröffentlicht - 2018
Peer-Review-StatusJa

Externe IDs

researchoutputwizard legacy.publication#82575
Scopus 85018749663
ORCID /0000-0002-5321-9343/work/142236697

Schlagworte

Schlagwörter

  • Probabilistic model checking, MTBDD, Variable reordering, Quantiles, LTL, Deterministic automata