The Library
On automated verification of probabilistic programs
Tools
Legay, Axel, Murawski, Andrzej S., Ouaknine, Joël and Worrell, James (2008) On automated verification of probabilistic programs. In: 14th International Conference on Tools and Algorithms for the Construction and Analysis of Systems (TACAS'08), Budapest, Hungary, 29 March - 6 April 2008. Published in: Lecture Notes in Computer Science, 4963 pp. 173-187. ISBN 9783540787990. doi:10.1007/978-3-540-78800-3_13 ISSN 0302-9743.
Research output not available from this repository.
Request-a-Copy directly from author or use local Library Get it For Me service.
Official URL: http://dx.doi.org/10.1007/978-3-540-78800-3_13
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.
Item Type: | Conference Item (Paper) | ||||
---|---|---|---|---|---|
Divisions: | Faculty of Science, Engineering and Medicine > Science > Computer Science | ||||
Journal or Publication Title: | Lecture Notes in Computer Science | ||||
Publisher: | Springer | ||||
ISBN: | 9783540787990 | ||||
ISSN: | 0302-9743 | ||||
Book Title: | Tools and Algorithms for the Construction and Analysis of Systems | ||||
Official Date: | 2008 | ||||
Dates: |
|
||||
Volume: | 4963 | ||||
Page Range: | pp. 173-187 | ||||
DOI: | 10.1007/978-3-540-78800-3_13 | ||||
Status: | Peer Reviewed | ||||
Publication Status: | Published | ||||
Access rights to Published version: | Restricted or Subscription Access | ||||
Conference Paper Type: | Paper | ||||
Title of Event: | 14th International Conference on Tools and Algorithms for the Construction and Analysis of Systems (TACAS'08) | ||||
Type of Event: | Conference | ||||
Location of Event: | Budapest, Hungary | ||||
Date(s) of Event: | 29 March - 6 April 2008 |
Request changes or add full text files to a record
Repository staff actions (login required)
View Item |