David Parker

David Parker

Lecturer
School of Computer Science
University of Birmingham
Edgbaston, Birmingham, B15 2TT

Email: d.a.parker@cs.bham.ac.uk
Tel: +44 (0) 121 41 47264
Office: 107
Office hours: Wed 12.30-1.30, Thu 3-4
<< NEWS >>
[DMP09] Alastair Donaldson, Alice Miller and David Parker. Language-level Symmetry Reduction for Probabilistic Model Checking. In Proc. 6th International Conference on Quantitative Evaluation of Systems (QEST'09), pages 289-298, IEEE Computer Society. September 2009. [pdf] [bib] [Presents symmetry reduction techniques based on translation of PRISM models.]
Downloads:  pdf pdf (248 KB)  bib bib
Notes: A full version of this paper, with proofs, is available.
Abstract. Symmetry reduction is a technique for combating state-space explosion in model checking. The generic representatives approach to symmetry reduction uses a language-level translation of symmetric models to a reduced form, making it straightforward to combine with existing tools and implementations. These techniques have been proposed for both non-probabilistic and probabilistic model checking, but are currently difficult to apply to complex models due to prohibitive restrictions in the modelling language. We present a much richer language, which allows specification of probabilistic systems in a way that guarantees the applicability of the generic representatives technique, together with an extended translation algorithm, and demonstrate the effectiveness of our techniques on a large set of case studies.