Probabilistic Output Analysis by Program Manipulation

Research output: Chapter in Book/Report/Conference proceedingArticle in proceedingsResearchpeer-review


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.
Original languageEnglish
Title of host publicationElectronic Proceedings in Theoretical Computer Science
Publication date29 Sep 2015
Publication statusPublished - 29 Sep 2015
EventQuantitative Aspects of Programming Languages and Systems - Queen Mary Unversity of London, London, United Kingdom
Duration: 11 Apr 201512 Apr 2015


ConferenceQuantitative Aspects of Programming Languages and Systems
LocationQueen Mary Unversity of London
CountryUnited Kingdom
Internet address
SeriesElectronic Proceedings in Theoretical Computer Science

Cite this