On the hardness of analyzing probabilistic programs

DOI10.1007/s00236-018-0321-1zbMath1417.68054OpenAlexW2803490327WikidataQ57800485 ScholiaQ57800485MaRDI QIDQ1733103

Joost-Pieter Katoen, Christoph Matheja, Benjamin Lucien Kaminski

Publication date: 21 March 2019

Published in: Acta Informatica (Search for Journal in Brave)

Full work available at URL: https://discovery.ucl.ac.uk/id/eprint/10089603/

Mathematics Subject Classification ID

Specification and verification (program logics, model checking, etc.) (68Q60) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Mathematical aspects of software engineering (specification, verification, metrics, requirements, etc.) (68N30) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87)

Related Items

Learning probabilistic termination proofs ⋮ Latticed \(k\)-induction with an application to probabilistic programs ⋮ Symbolic computation in automated program reasoning ⋮ Automatic Generation of Moment-Based Invariants for Prob-Solvable Loops ⋮ Deciding Fast Termination for Probabilistic VASS with Nondeterminism ⋮ Densities of almost surely terminating probabilistic programs are differentiable almost everywhere ⋮ Generating functions for probabilistic programs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A probabilistic PDL
• Semantics of probabilistic programs
• Classical recursion theory. The theory of functions and sets of natural numbers.
• Classical recursion theory. Vol. II
• Inferring covariances for probabilistic programs
• Probabilistic termination versus fair termination
• Probability theory. A comprehensive course.
• Probabilistic NetKAT
• Weakest Precondition Reasoning for Expected Run–Times of Probabilistic Programs
• Probabilistic Termination
• Algorithmic analysis of qualitative and quantitative termination problems for affine probabilistic programs
• Probabilistic relational reasoning for differential privacy
• On the Hardness of Almost–Sure Termination
• Probabilistic Termination by Monadic Affine Sized Typing
• Verification of Probabilistic Programs
• Computational Complexity of Probabilistic Turing Machines
• Termination Analysis of Probabilistic Programs Through Positivstellensatz’s
• Abstraction, Refinement and Proof for Probabilistic Systems
• Termination of Probabilistic Concurrent Program
• Probabilistic Termination of CHRiSM Programs
• Linear-Invariant Generation for Probabilistic Programs:
• Term Rewriting and Applications
• Recursive Predicates and Quantifiers
• Recursively enumerable sets of positive integers and their decision problems
• Smoothed Complexity Theory
• CONCUR 2005 – Concurrency Theory
• Conditioning in probabilistic programming