Verification of Probabilistic Programs
Authors:
- 1 May 1984
- journal article
- research article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Computing
- Vol. 13 (2) , 292-314
Abstract
A general method for proving properties of probabilistic programs is presented. This method generalizes the intermediate assertion method in that it extends a given assertion on the output distribution into an invariant assertion on all intermediate distributions, too. The proof method is shown to be sound and complete for programs which terminate with probability 1. A dual approach, based on the expected number of visits in each intermediate state, is also presented. All the methods are presented under the uniform framework which considers a probabilistic program as a discrete Markov process.Keywords
This publication has 9 references indexed in Scilit:
- Termination of probabilistic concurrent programs1982
- On the andvantages of free choice1981
- Logics for probabilistic programming (Extended Abstract)1980
- Semantics of probabilistic programs1979
- Probabilistic LCF1978
- Subgoal inductionCommunications of the ACM, 1977
- Verifying Program PerformanceJournal of the ACM, 1976
- Denumerable Markov Chains1976
- Assigning meanings to programs1967