On Automated Verification of Probabilistic Programs
Lists
Only you see this
Abstract
We introduce a simple procedural probabilistic programming language which is suitable for coding a wide variety of randomised algorithms and protocols. This language is interpreted over finite datatypes and has a decidable equivalence problem. We have implemented an automated equivalence checker, which we call apex, for this language, based on game semantics. We illustrate our approach with three non-trivial case studies: (i) Herman’s self-stabilisation algorithm; (ii) an analysis of the average shape of binary search trees obtained by certain sequences of random insertions and deletions; and (iii) the problem of anonymity in the Dining Cryptographers protocol. In particular, we record an exponential speed-up in the latter over state-of-the-art competing approaches.
BibTeX
@inproceedings{legay2008automated,
author = {Axel Legay and Andrzej S. Murawski and Joël Ouaknine and James Worrell},
title = {{On Automated Verification of Probabilistic Programs}},
booktitle = {TACAS},
year = {2008},
doi = {10.1007/978-3-540-78800-3\_13},
}Loading related content...