Probabilistic CEGAR 1st edtion by Holger
Hermanns, Björn Wachter, Lijun Zhang ISBN
3540705437 9783540705437 pdf download
https://ebookball.com/product/probabilistic-cegar-1st-edtion-by-
holger-hermanns-bjaprn-wachter-lijun-zhang-
isbn-3540705437-9783540705437-9308/
Explore and download more ebooks or textbooks
at ebookball.com
, Get Your Digital Files Instantly: PDF, ePub, MOBI and More
Quick Digital Downloads: PDF, ePub, MOBI and Other Formats
Singularity Designing Better Software Invited Talk 1st edtion by James
Larus ISBN 3540705437 9783540705437
https://ebookball.com/product/singularity-designing-better-
software-invited-talk-1st-edtion-by-james-larus-
isbn-3540705437-9783540705437-8774/
Coping with Outside the Box Attacks 1st edtion by Edward Felten ISBN
3540705437 9783540705437
https://ebookball.com/product/coping-with-outside-the-box-
attacks-1st-edtion-by-edward-felten-
isbn-3540705437-9783540705437-10832/
CSIsat Interpolation for LA EUF 1st edtion by Dirk Beyer, Damien
Zufferey, Rupak Majumdar ISBN 3540705437 9783540705437
https://ebookball.com/product/csisat-interpolation-for-la-
euf-1st-edtion-by-dirk-beyer-damien-zufferey-rupak-majumdar-
isbn-3540705437-9783540705437-11084/
Reducing Concurrent Analysis Under a Context Bound to Sequential
Analysis 1st edtion by Akash Lal, Thomas Reps ISBN 3540705437
9783540705437
https://ebookball.com/product/reducing-concurrent-analysis-under-
a-context-bound-to-sequential-analysis-1st-edtion-by-akash-lal-
thomas-reps-isbn-3540705437-9783540705437-14174/
,Functional Verification of Power Gated Designs by Compositional
Reasoning 1st edtion by Cindy Eisner, Amir Nahir, Karen Yorav ISBN
3540705437 9783540705437
https://ebookball.com/product/functional-verification-of-power-
gated-designs-by-compositional-reasoning-1st-edtion-by-cindy-
eisner-amir-nahir-karen-yorav-
isbn-3540705437-9783540705437-11838/
Efficient Craig Interpolation for Linear Diophantine DisEquations and
Linear Modular Equations 1st edtion by Himanshu Jain, Edmund Clarke,
Orna Grumberg ISBN 3540705437 9783540705437
https://ebookball.com/product/efficient-craig-interpolation-for-
linear-diophantine-disequations-and-linear-modular-equations-1st-
edtion-by-himanshu-jain-edmund-clarke-orna-grumberg-
isbn-3540705437-9783540705437-9348/
FShell Systematic Test Case Generation for Dynamic Analysis and
Measurement 1st edtion by Andreas Holzer, Christian Schallhart,
Michael Tautschnig, Helmut Veith ISBN 3540705437 9783540705437
https://ebookball.com/product/fshell-systematic-test-case-
generation-for-dynamic-analysis-and-measurement-1st-edtion-by-
andreas-holzer-christian-schallhart-michael-tautschnig-helmut-
veith-isbn-3540705437-9783540705437-13804/
Scalable Shape Analysis for Systems Code 1st edtion by Hongseok Yang,
Oukseh Lee, Josh Berdine, Cristiano Calcagno, Byron Cook, Dino
Distefano, Peter O’Hearn ISBN 3540705437 9783540705437
https://ebookball.com/product/scalable-shape-analysis-for-
systems-code-1st-edtion-by-hongseok-yang-oukseh-lee-josh-berdine-
cristiano-calcagno-byron-cook-dino-distefano-peter-oaeurtmhearn-
isbn-3540705437-9783540705437-9282/
TORMCA Tool for Regular Model Checking 1st edition by Axel Legay ISBN
3540705437 9783540705437
https://ebookball.com/product/tormca-tool-for-regular-model-
checking-1st-edition-by-axel-legay-
isbn-3540705437-9783540705437-13428/
, Probabilistic CEGAR
Holger Hermanns, Björn Wachter, and Lijun Zhang
Universität des Saarlandes, Saarbrücken, Germany
{hermanns,bwachter,zhang}@cs.uni-sb.de
Abstract. Counterexample-guided abstraction refinement (CEGAR)
has been en vogue for the automatic verification of very large systems
in the past years. When trying to apply CEGAR to the verification of
probabilistic systems, various foundational questions arise. This paper
explores them in the context of predicate abstraction.
1 Introduction
Probabilistic behavioral descriptions are widely used to analyze and verify sys-
tems that exhibit “quantified uncertainty”, such as embedded, networked, or bio-
logical systems. The semantic model for such systems often are Markov chains or
Markov decision processes. We here consider homogeneous discrete-time Markov
chains (MCs) and Markov decision processes (MDPs). Properties of these sys-
tems can be specified by formulas in temporal logics such as PCTL [1], where for
instance quantitative probabilistic reachability (“the probability to reach a set
of bad states is at most 3%”) is expressible. Model checking algorithms for such
logics have been devised mainly for finite-state MCs [1] and MDPs [2], and effec-
tive tool support is provided by probabilistic model checkers such as Prism [3] or
Mrmc [4]. Despite its remarkable versatility, the approach is limited by the state
explosion problem, aggravated by the cost of numerical computation compared
to Boolean CTL model checking.
Predicate abstraction [5] is a method for creating finite abstract models of
non-probabilistic systems where symbolic expressions, so-called predicates, in-
duce a partitioning of its (potentially infinite) state space into a finite number of
regions. For automation, it is typically coupled [6,7] with counterexample-guided
abstraction refinement (CEGAR) [8] where an initially very coarse abstraction
is refined using diagnostic information (predicates) derived from abstract coun-
terexamples, until either the property is proved or refuted.
In this paper, we discuss how counterexample-guided abstraction refinement
can be developed in a probabilistic setting. Predicate abstraction without ab-
straction refinement has been presented in [9] for a guarded command language
whose concrete semantics maps to MDPs – more precisely, to probabilistic au-
tomata [10]. This is the natural basis for our present work. We restrict our
This work is supported by DFG as part of the Transregional Collaborative Research
Center SFB/TR 14 AVACS and by the NWO-DFG bilateral project VOSS.
A. Gupta and S. Malik (Eds.): CAV 2008, LNCS 5123, pp. 162–175, 2008.
c Springer-Verlag Berlin Heidelberg 2008
Hermanns, Björn Wachter, Lijun Zhang ISBN
3540705437 9783540705437 pdf download
https://ebookball.com/product/probabilistic-cegar-1st-edtion-by-
holger-hermanns-bjaprn-wachter-lijun-zhang-
isbn-3540705437-9783540705437-9308/
Explore and download more ebooks or textbooks
at ebookball.com
, Get Your Digital Files Instantly: PDF, ePub, MOBI and More
Quick Digital Downloads: PDF, ePub, MOBI and Other Formats
Singularity Designing Better Software Invited Talk 1st edtion by James
Larus ISBN 3540705437 9783540705437
https://ebookball.com/product/singularity-designing-better-
software-invited-talk-1st-edtion-by-james-larus-
isbn-3540705437-9783540705437-8774/
Coping with Outside the Box Attacks 1st edtion by Edward Felten ISBN
3540705437 9783540705437
https://ebookball.com/product/coping-with-outside-the-box-
attacks-1st-edtion-by-edward-felten-
isbn-3540705437-9783540705437-10832/
CSIsat Interpolation for LA EUF 1st edtion by Dirk Beyer, Damien
Zufferey, Rupak Majumdar ISBN 3540705437 9783540705437
https://ebookball.com/product/csisat-interpolation-for-la-
euf-1st-edtion-by-dirk-beyer-damien-zufferey-rupak-majumdar-
isbn-3540705437-9783540705437-11084/
Reducing Concurrent Analysis Under a Context Bound to Sequential
Analysis 1st edtion by Akash Lal, Thomas Reps ISBN 3540705437
9783540705437
https://ebookball.com/product/reducing-concurrent-analysis-under-
a-context-bound-to-sequential-analysis-1st-edtion-by-akash-lal-
thomas-reps-isbn-3540705437-9783540705437-14174/
,Functional Verification of Power Gated Designs by Compositional
Reasoning 1st edtion by Cindy Eisner, Amir Nahir, Karen Yorav ISBN
3540705437 9783540705437
https://ebookball.com/product/functional-verification-of-power-
gated-designs-by-compositional-reasoning-1st-edtion-by-cindy-
eisner-amir-nahir-karen-yorav-
isbn-3540705437-9783540705437-11838/
Efficient Craig Interpolation for Linear Diophantine DisEquations and
Linear Modular Equations 1st edtion by Himanshu Jain, Edmund Clarke,
Orna Grumberg ISBN 3540705437 9783540705437
https://ebookball.com/product/efficient-craig-interpolation-for-
linear-diophantine-disequations-and-linear-modular-equations-1st-
edtion-by-himanshu-jain-edmund-clarke-orna-grumberg-
isbn-3540705437-9783540705437-9348/
FShell Systematic Test Case Generation for Dynamic Analysis and
Measurement 1st edtion by Andreas Holzer, Christian Schallhart,
Michael Tautschnig, Helmut Veith ISBN 3540705437 9783540705437
https://ebookball.com/product/fshell-systematic-test-case-
generation-for-dynamic-analysis-and-measurement-1st-edtion-by-
andreas-holzer-christian-schallhart-michael-tautschnig-helmut-
veith-isbn-3540705437-9783540705437-13804/
Scalable Shape Analysis for Systems Code 1st edtion by Hongseok Yang,
Oukseh Lee, Josh Berdine, Cristiano Calcagno, Byron Cook, Dino
Distefano, Peter O’Hearn ISBN 3540705437 9783540705437
https://ebookball.com/product/scalable-shape-analysis-for-
systems-code-1st-edtion-by-hongseok-yang-oukseh-lee-josh-berdine-
cristiano-calcagno-byron-cook-dino-distefano-peter-oaeurtmhearn-
isbn-3540705437-9783540705437-9282/
TORMCA Tool for Regular Model Checking 1st edition by Axel Legay ISBN
3540705437 9783540705437
https://ebookball.com/product/tormca-tool-for-regular-model-
checking-1st-edition-by-axel-legay-
isbn-3540705437-9783540705437-13428/
, Probabilistic CEGAR
Holger Hermanns, Björn Wachter, and Lijun Zhang
Universität des Saarlandes, Saarbrücken, Germany
{hermanns,bwachter,zhang}@cs.uni-sb.de
Abstract. Counterexample-guided abstraction refinement (CEGAR)
has been en vogue for the automatic verification of very large systems
in the past years. When trying to apply CEGAR to the verification of
probabilistic systems, various foundational questions arise. This paper
explores them in the context of predicate abstraction.
1 Introduction
Probabilistic behavioral descriptions are widely used to analyze and verify sys-
tems that exhibit “quantified uncertainty”, such as embedded, networked, or bio-
logical systems. The semantic model for such systems often are Markov chains or
Markov decision processes. We here consider homogeneous discrete-time Markov
chains (MCs) and Markov decision processes (MDPs). Properties of these sys-
tems can be specified by formulas in temporal logics such as PCTL [1], where for
instance quantitative probabilistic reachability (“the probability to reach a set
of bad states is at most 3%”) is expressible. Model checking algorithms for such
logics have been devised mainly for finite-state MCs [1] and MDPs [2], and effec-
tive tool support is provided by probabilistic model checkers such as Prism [3] or
Mrmc [4]. Despite its remarkable versatility, the approach is limited by the state
explosion problem, aggravated by the cost of numerical computation compared
to Boolean CTL model checking.
Predicate abstraction [5] is a method for creating finite abstract models of
non-probabilistic systems where symbolic expressions, so-called predicates, in-
duce a partitioning of its (potentially infinite) state space into a finite number of
regions. For automation, it is typically coupled [6,7] with counterexample-guided
abstraction refinement (CEGAR) [8] where an initially very coarse abstraction
is refined using diagnostic information (predicates) derived from abstract coun-
terexamples, until either the property is proved or refuted.
In this paper, we discuss how counterexample-guided abstraction refinement
can be developed in a probabilistic setting. Predicate abstraction without ab-
straction refinement has been presented in [9] for a guarded command language
whose concrete semantics maps to MDPs – more precisely, to probabilistic au-
tomata [10]. This is the natural basis for our present work. We restrict our
This work is supported by DFG as part of the Transregional Collaborative Research
Center SFB/TR 14 AVACS and by the NWO-DFG bilateral project VOSS.
A. Gupta and S. Malik (Eds.): CAV 2008, LNCS 5123, pp. 162–175, 2008.
c Springer-Verlag Berlin Heidelberg 2008
