PCTL Model Checking of Markov Chains: Truth and Falsity as Winning Strategies in Games
File(s)truth-falsity-pctl-markov-chain.pdf (504.02 KB)
Submitted version
Author(s)
Wagner, D
Piterman, N
Huth, M
Fecher, H
Type
Journal Article
Abstract
Probabilistic model checking is a technique for verifying whether a model such as a Markov chain satisfies a probabilistic, behavioral property û e.g. ôwith probability at least 0.999, a device will be elected leader.ö Such properties are expressible in probabilistic temporal logics, e.g. PCTL, and efficient algorithms exist for checking whether these formulae are true or false on infinite-state models. Alas, these algorithms do not supply diagnostic information for why a probabilistic property does or does not hold in a given model. We provide here complete and rigorous foundations for such diagnostics in the setting of countable labeled Markov chains and PCTL. For each model and PCTL formula, we define a game between a Verifier and a Refuter that is won by Verifier if the formula holds in the model, and won by Refuter if it does not hold. Games are won by exactly one player, through monotone strategies that encode the diagnostic information for truth and falsity (respectively). These games are infinite with Buechi type acceptance conditions where simpler fairness conditions are shown to be not sufficient. Verifier can always force finite plays for certain PCTL formulae, suggesting the existence of finite-state abstractions of models that satisfy such formulae. \r\n
Date Issued
2009
Citation
Performance Evaluation, 2009, 67 (9), pp.858-872
ISSN
0166-5316
Publisher
Elsevier
Start Page
858
End Page
872
Journal / Book Title
Performance Evaluation
Volume
67
Issue
9
Copyright Statement
© 2009 Elsevier B.V. All rights reserved. NOTICE: this is the author’s version of a work that was submitted for publication in Performance Evaluation. Changes resulting from the publishing process, such as peer review, editing, corrections, structural formatting, and other quality control mechanisms may not be reflected in this document. Changes may have been made to this work since it was submitted for publication. A definitive version was subsequently published in PERFORMANCE EVALUATION, VOL:67, ISSUE:9, (2009) DOI:10.1016/j.peva.2009.07.002
Source Volume Number
67