Probabilistic abstract interpretation: From trace semantics to DTMC’s and linear regression
File(s)Festschrift15.pdf (379.07 KB)
Accepted version
Author(s)
Di Pierro, A
Wiklicky, H
Type
Chapter
Abstract
In order to perform probabilistic program analysis we need to consider probabilistic languages or languages with a probabilistic semantics, as well as a corresponding framework for the analysis which is able to accommodate probabilistic properties and properties of probabilistic computations. To this purpose we investigate the relationship between three different types of probabilistic semantics for a core imperative language, namely Kozen’s Fixpoint Semantics, our Linear Operator Semantics and probabilistic versions of Maximal Trace Semantics. We also discuss the relationship between Probabilistic Abstract Interpretation (PAI) and statistical or linear regression analysis. While classical Abstract Interpretation, based on Galois connection, allows only for worst-case analyses, the use of the Moore-Penrose pseudo inverse in PAI opens the possibility of exploiting statistical and noisy observations in order to analyse and identify various system properties.
Editor(s)
Probst, Christian W
Hankin, Chris
Hansen, René Rydhof
Date Issued
2015-12-25
Citation
Essays Dedicated to Hanne Riis Nielson and Flemming Nielson on the Occasion of Their 60th Birthdays, 2015, 9560, pp.111-139
ISBN
9783319278094
Publisher
Springer
Start Page
111
End Page
139
Journal / Book Title
Essays Dedicated to Hanne Riis Nielson and Flemming Nielson on the Occasion of Their 60th Birthdays
Lecture Notes in Computer Science
Volume
9560
Copyright Statement
© Springer International Publishing Switzerland 2016. The final publication is available at Springer via https://dx.doi.org/10.1007/978-3-319-27810-0_6
Subjects
Science & Technology
Technology
Computer Science, Software Engineering
Computer Science, Theory & Methods
Computer Science
LAMBDA-CALCULUS
PRECISION
Artificial Intelligence & Image Processing
Publication Status
Published
Date Publish Online
2015-12-25