Probabilistic Output Analysis by Program Manipulation

Publikation: Bidrag til bog/antologi/rapportKonferencebidrag i proceedingsForskningpeer 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.
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