Modeling and Verification of Probabilistic Systems


  • 15.02.2021: We are online.




The aim of this course is to address the compositional modeling and the automated verification (i.e., model checking) of probabilistic models. These models are important for addressing performance aspects, they are the key to randomised distributed algorithms, and have applications in systems biology as well as security, to mention a few. This course is about:

  1. How to obtain models for complex systems that involve random aspects?
  2. How to verify in a fully algorithmic manner, whether such models satisfy basic properties, such as reachability probabilities?
  3. Can we make these models smaller to enable or simplify their verification?
  4. What kind of practical problems can be treated in this manner?

If you’d like to have an introductory read on this lecture, then you might consider to read the paper “Model Checking Meets Probability: A Gentle Introduction” by Joost-Pieter Katoen. Moreover, the paper “Performance Evaluation and Model Checking Join Forces”  published in Communications of the ACM (2010) might be of interest.


Markov chains, Markov decision processes, probabilistic automata, Markov automata (aka: continuous-time MDPs), model checking, probabilistic temporal logic (probabilistic CTL and LTL), bisimulation, compositional modeling, concurrency, compositional minimisation.

Additional background literature

  • C. Baier and J.-P. Katoen. Principles of Model Checking, MIT Press, 2008 [Chapter 10].
  • H.C. Tijms: A First Course in Stochastic Models. Wiley, 2003.
  • J.-P. Katoen. The Probabilistic Model Checking Landscape. LICS 2016.
  • H. Hermanns: Interactive Markov Chains: The Quest for Quantified Quality. LNCS 2428, Springer 2002.
  • E. Brinksma, H. Hermanns, J.-P. Katoen: Lectures on Formal Methods and Performance Analysis. LNCS 2090, Springer 2001.
  • M. Stoelinga: Introduction to Probabilistic Automata. Bulletin of the EATCS 78. 2002
  • M. Timmer: Efficient Modelling, Generation and Analysis of Markov Automata. Chapter 3. 2013