Verifying the evolution of probability distributions governed by a DTMC

Youngmin Kwon, Gul Agha

Research output: Contribution to journalArticlepeer-review

Abstract

We propose a new probabilistic temporal logic, iLTL, which captures properties of systems whose state can be represented by probability mass functions (pmfs). Using iLTL, we can specify reachability to a state (i.e., a pmf), as well as properties representing the aggregate (expected) behavior of a system. We then consider a class of systems whose transitions are governed by a Markov Chain-in this case, the set of states a system may be in is specified by the transitions of pmfs from all potential initial states to the final state. We then provide a model checking algorithm to check iLTL properties of such systems. Unlike existing model checking techniques, which either compute the portions of the computational paths that satisfy a specification or evaluate properties along a single path of pmf transitions, our model checking technique enables us to do a complete analysis on the expected behaviors of large-scale systems. Desirable system parameters may also be found as a counterexample of a negated goal. Finally, we illustrate the usefulness of iLTL model checking by means of two examples: assessing software reliability and ensuring the results of administering a drug.

Original languageEnglish (US)
Article number5557891
Pages (from-to)126-141
Number of pages16
JournalIEEE Transactions on Software Engineering
Volume37
Issue number1
DOIs
StatePublished - Jan 1 2011

Keywords

  • Discrete Time Markov Chain
  • Probabilistic model checking
  • linear temporal logic
  • pharmacokinetics

ASJC Scopus subject areas

  • Software

Fingerprint Dive into the research topics of 'Verifying the evolution of probability distributions governed by a DTMC'. Together they form a unique fingerprint.

Cite this