Bounded expectations: resource analysis for probabilistic programs
VC Ngo, Q Carbonneaux, J Hoffmann - ACM SIGPLAN Notices, 2018 - dl.acm.org
This paper presents a new static analysis for deriving upper bounds on the expected
resource consumption of probabilistic programs. The analysis is fully automatic and derives …
resource consumption of probabilistic programs. The analysis is fully automatic and derives …
Probabilistic termination: Soundness, completeness, and compositionality
LM Ferrer Fioriti, H Hermanns - Proceedings of the 42nd Annual ACM …, 2015 - dl.acm.org
We propose a framework to prove almost sure termination for probabilistic programs with
real valued variables. It is based on ranking supermartingales, a notion analogous to …
real valued variables. It is based on ranking supermartingales, a notion analogous to …
[PDF][PDF] A new proof rule for almost-sure termination
We present a new proof rule for proving almost-sure termination of probabilistic programs,
including those that contain demonic non-determinism. An important question for a …
including those that contain demonic non-determinism. An important question for a …
Reasoning about recursive probabilistic programs
This paper presents a wp--style calculus for obtaining expectations on the outcomes of
(mutually) recursive probabilistic programs. We provide several proof rules to derive one …
(mutually) recursive probabilistic programs. We provide several proof rules to derive one …
Lexicographic ranking supermartingales: an efficient approach to termination of probabilistic programs
Probabilistic programs extend classical imperative programs with real-valued random
variables and random branching. The most basic liveness property for such programs is the …
variables and random branching. The most basic liveness property for such programs is the …
Lilac: a modal separation logic for conditional probability
We present Lilac, a separation logic for reasoning about probabilistic programs where
separating conjunction captures probabilistic independence. Inspired by an analogy with …
separating conjunction captures probabilistic independence. Inspired by an analogy with …
Probabilistic program verification via inductive synthesis of inductive invariants
Essential tasks for the verification of probabilistic programs include bounding expected
outcomes and proving termination in finite expected runtime. We contribute a simple yet …
outcomes and proving termination in finite expected runtime. We contribute a simple yet …
Advanced weakest precondition calculi for probabilistic programs
BL Kaminski - 2019 - discovery.ucl.ac.uk
Wir studieren die quantitative Analyse probabilistischer Programme. Dabei untersuchen wir
vornehmlich zwei Aspekte: Die Analysetechniken selbst, sowie die komplexitäts-bzw …
vornehmlich zwei Aspekte: Die Analysetechniken selbst, sowie die komplexitäts-bzw …
Quantitative separation logic: a logic for reasoning about probabilistic pointer programs
We present quantitative separation logic (QSL). In contrast to classical separation logic, QSL
employs quantities which evaluate to real numbers instead of predicates which evaluate to …
employs quantities which evaluate to real numbers instead of predicates which evaluate to …
Symbolic execution for randomized programs
Z Susag, S Lahiri, J Hsu, S Roy - Proceedings of the ACM on …, 2022 - dl.acm.org
We propose a symbolic execution method for programs that can draw random samples. In
contrast to existing work, our method can verify randomized programs with unknown inputs …
contrast to existing work, our method can verify randomized programs with unknown inputs …