Probabilistic Output Analysis by Program Manipulation

Mads Rosendahl
(Roskilde University, Denmark)
Maja H. Kirkeby
(Roskilde University, Denmark)

The aim of a probabilistic output analysis is to derive a probability distribution of possible output values for a program from a probability distribution of its input. We present a method for performing static output analysis, based on program transformation techniques. It generates a probability function as a possibly uncomputable expression in an intermediate language. This program is then analyzed, transformed, and approximated. The result is a closed form expression that computes an over approximation of the output probability distribution for the program. We focus on programs where the possible input follows a known probability distribution. Tests in programs are not assumed to satisfy the Markov property of having fixed branching probabilities independently of previous history.

In Nathalie Bertrand and Mirco Tribastone: Proceedings Thirteenth Workshop on Quantitative Aspects of Programming Languages and Systems (QAPL 2015), London, UK, 11th-12th April 2015, Electronic Proceedings in Theoretical Computer Science 194, pp. 110–124.
Published: 28th September 2015.

ArXived at: https://dx.doi.org/10.4204/EPTCS.194.8 bibtex PDF
References in reconstructed bibtex, XML and HTML format (approximated).
Comments and questions to: eptcs@eptcs.org
For website issues: webmaster@eptcs.org