Probabilistic Output Analysis by Program Manipulation

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

Abstract

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.
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.
LanguageEnglish
Title of host publicationElectronic Proceedings in Theoretical Computer Science
Volume194
Date29 Sep 2015
Pages110-124
DOIs
StatePublished - 29 Sep 2015
EventQuantitative Aspects of Programming Languages and Systems - Queen Mary Unversity of London, London, United Kingdom
Duration: 11 Apr 201512 Apr 2015
http://qapl15.inria.fr/

Conference

ConferenceQuantitative Aspects of Programming Languages and Systems
LocationQueen Mary Unversity of London
CountryUnited Kingdom
CityLondon
Period11/04/201512/04/2015
Internet address
SeriesElectronic Proceedings in Theoretical Computer Science
Number194
ISSN2075-2180

Cite this

Rosendahl, M., & Kirkeby, M. H. (2015). Probabilistic Output Analysis by Program Manipulation. In Electronic Proceedings in Theoretical Computer Science (Vol. 194, pp. 110-124). Electronic Proceedings in Theoretical Computer Science, No. 194, DOI: 10.4204/EPTCS.194.8
Rosendahl, Mads ; Kirkeby, Maja Hanne. / Probabilistic Output Analysis by Program Manipulation. Electronic Proceedings in Theoretical Computer Science. Vol. 194 2015. pp. 110-124 (Electronic Proceedings in Theoretical Computer Science; No. 194).
@inproceedings{cdedbab0928f42fbad730b87325c666f,
title = "Probabilistic Output Analysis by Program Manipulation",
abstract = "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.",
author = "Mads Rosendahl and Kirkeby, {Maja Hanne}",
year = "2015",
month = "9",
day = "29",
doi = "10.4204/EPTCS.194.8",
language = "English",
volume = "194",
pages = "110--124",
booktitle = "Electronic Proceedings in Theoretical Computer Science",

}

Rosendahl, M & Kirkeby, MH 2015, Probabilistic Output Analysis by Program Manipulation. in Electronic Proceedings in Theoretical Computer Science. vol. 194, Electronic Proceedings in Theoretical Computer Science, no. 194, pp. 110-124, London, United Kingdom, 11/04/2015. DOI: 10.4204/EPTCS.194.8

Probabilistic Output Analysis by Program Manipulation. / Rosendahl, Mads; Kirkeby, Maja Hanne.

Electronic Proceedings in Theoretical Computer Science. Vol. 194 2015. p. 110-124.

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

TY - GEN

T1 - Probabilistic Output Analysis by Program Manipulation

AU - Rosendahl,Mads

AU - Kirkeby,Maja Hanne

PY - 2015/9/29

Y1 - 2015/9/29

N2 - 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.

AB - 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.

UR - http://eptcs.web.cse.unsw.edu.au/paper.cgi?QAPL2015.8

U2 - 10.4204/EPTCS.194.8

DO - 10.4204/EPTCS.194.8

M3 - Article in proceedings

VL - 194

SP - 110

EP - 124

BT - Electronic Proceedings in Theoretical Computer Science

ER -

Rosendahl M, Kirkeby MH. Probabilistic Output Analysis by Program Manipulation. In Electronic Proceedings in Theoretical Computer Science. Vol. 194. 2015. p. 110-124. (Electronic Proceedings in Theoretical Computer Science; No. 194). Available from, DOI: 10.4204/EPTCS.194.8