On the hardness of analyzing probabilistic programs
DOI10.1007/S00236-018-0321-1zbMATH Open1417.68054OpenAlexW2803490327WikidataQ57800485 ScholiaQ57800485MaRDI QIDQ1733103FDOQ1733103
Authors: Benjamin Lucien Kaminski, Joost-Pieter Katoen, Christoph Matheja 
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/
Recommendations
- On the hardness of almost-sure termination
- Algorithmic analysis of qualitative and quantitative termination problems for affine probabilistic programs
- Inferring covariances for probabilistic programs
- Weakest precondition reasoning for expected run-times of probabilistic programs
- Probabilistic termination versus fair termination
Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Mathematical aspects of software engineering (specification, verification, metrics, requirements, etc.) (68N30) Specification and verification (program logics, model checking, etc.) (68Q60)
Cites Work
- Probability theory. A comprehensive course.
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- A probabilistic PDL
- Title not available (Why is that?)
- Computational Complexity of Probabilistic Turing Machines
- Abstraction, Refinement and Proof for Probabilistic Systems
- Title not available (Why is that?)
- Semantics of probabilistic programs
- Classical recursion theory. Vol. II
- Recursively enumerable sets of positive integers and their decision problems
- Classical recursion theory. The theory of functions and sets of natural numbers.
- Recursive Predicates and Quantifiers
- CONCUR 2005 – Concurrency Theory
- Probabilistic relational reasoning for differential privacy
- Title not available (Why is that?)
- Probabilistic termination: soundness, completeness, and compositionality
- Algorithmic analysis of qualitative and quantitative termination problems for affine probabilistic programs
- Linear-invariant generation for probabilistic programs: automated support for proof-based methods
- Verification of Probabilistic Programs
- Termination of Probabilistic Concurrent Program
- Probabilistic termination versus fair termination
- Termination analysis of probabilistic programs through Positivstellensatz's
- Term Rewriting and Applications
- Inferring covariances for probabilistic programs
- Probabilistic termination of CHRiSM programs
- Probabilistic NetKAT
- Weakest precondition reasoning for expected run-times of probabilistic programs
- On the hardness of almost-sure termination
- Probabilistic termination by monadic affine sized typing
- Title not available (Why is that?)
- Conditioning in probabilistic programming
Cited In (21)
- Probabilistic termination versus fair termination
- Automatic Generation of Moment-Based Invariants for Prob-Solvable Loops
- Learning probabilistic termination proofs
- Latticed \(k\)-induction with an application to probabilistic programs
- On the hardness of almost-sure termination
- Weakest precondition reasoning for expected run-times of probabilistic programs
- Generating functions for probabilistic programs
- Universal equivalence and majority of probabilistic programs over finite fields
- Densities of almost surely terminating probabilistic programs are differentiable almost everywhere
- Symbolic computation in automated program reasoning
- Algorithmic analysis of qualitative and quantitative termination problems for affine probabilistic programs
- On lexicographic proof rules for probabilistic termination
- Analysis-aware defeaturing: Problem setting and a posteriori estimation
- Probabilistic unifying relations for modelling epistemic and aleatoric uncertainty: semantics and automated reasoning with theorem proving
- Does a Program Yield the Right Distribution?
- Probabilistic verification beyond context-freeness
- Program analysis is harder than verification: a computability perspective
- Inferring covariances for probabilistic programs
- Probabilistic program verification via inductive synthesis of inductive invariants
- On probabilistic techniques for data flow analysis
- Deciding fast termination for probabilistic VASS with nondeterminism
This page was built for publication: On the hardness of analyzing probabilistic programs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1733103)
