Probabilistic Output Analysis by Program Manipulation

Publikation: Bidrag til bog/antologi/rapportKonferencebidrag i proceedingsForskningpeer review

Resumé

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.
OriginalsprogEngelsk
TitelElectronic Proceedings in Theoretical Computer Science
Vol/bind194
Publikationsdato29 sep. 2015
Sider110-124
DOI
StatusUdgivet - 29 sep. 2015
BegivenhedQuantitative Aspects of Programming Languages and Systems - Queen Mary Unversity of London, London, Storbritannien
Varighed: 11 apr. 201512 apr. 2015
http://qapl15.inria.fr/

Konference

KonferenceQuantitative Aspects of Programming Languages and Systems
LokationQueen Mary Unversity of London
LandStorbritannien
ByLondon
Periode11/04/201512/04/2015
Internetadresse
NavnElectronic Proceedings in Theoretical Computer Science
Nummer194
ISSN2075-2180

Citer dette

Rosendahl, M., & Kirkeby, M. H. (2015). Probabilistic Output Analysis by Program Manipulation. I Electronic Proceedings in Theoretical Computer Science (Bind 194, s. 110-124). Electronic Proceedings in Theoretical Computer Science, Nr. 194 https://doi.org/10.4204/EPTCS.194.8
Rosendahl, Mads ; Kirkeby, Maja Hanne. / Probabilistic Output Analysis by Program Manipulation. Electronic Proceedings in Theoretical Computer Science. Bind 194 2015. s. 110-124 (Electronic Proceedings in Theoretical Computer Science; Nr. 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. i Electronic Proceedings in Theoretical Computer Science. bind 194, Electronic Proceedings in Theoretical Computer Science, nr. 194, s. 110-124, Quantitative Aspects of Programming Languages and Systems, London, Storbritannien, 11/04/2015. https://doi.org/10.4204/EPTCS.194.8

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

Electronic Proceedings in Theoretical Computer Science. Bind 194 2015. s. 110-124 (Electronic Proceedings in Theoretical Computer Science; Nr. 194).

Publikation: Bidrag til bog/antologi/rapportKonferencebidrag i proceedingsForskningpeer 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. I Electronic Proceedings in Theoretical Computer Science. Bind 194. 2015. s. 110-124. (Electronic Proceedings in Theoretical Computer Science; Nr. 194). https://doi.org/10.4204/EPTCS.194.8