On the hardness of analyzing probabilistic programs
From MaRDI portal
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)
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
Cites work
- scientific article; zbMATH DE number 3131080 (Why is no real title available?)
- scientific article; zbMATH DE number 3574936 (Why is no real title available?)
- scientific article; zbMATH DE number 610968 (Why is no real title available?)
- scientific article; zbMATH DE number 1956507 (Why is no real title available?)
- scientific article; zbMATH DE number 2043521 (Why is no real title available?)
- scientific article; zbMATH DE number 1416652 (Why is no real title available?)
- scientific article; zbMATH DE number 5685899 (Why is no real title available?)
- scientific article; zbMATH DE number 3291134 (Why is no real title available?)
- A probabilistic PDL
- Abstraction, Refinement and Proof for Probabilistic Systems
- Algorithmic analysis of qualitative and quantitative termination problems for affine probabilistic programs
- CONCUR 2005 – Concurrency Theory
- Classical recursion theory. The theory of functions and sets of natural numbers.
- Classical recursion theory. Vol. II
- Computational Complexity of Probabilistic Turing Machines
- Conditioning in probabilistic programming
- Inferring covariances for probabilistic programs
- Linear-invariant generation for probabilistic programs: automated support for proof-based methods
- On the hardness of almost-sure termination
- Probabilistic NetKAT
- Probabilistic relational reasoning for differential privacy
- Probabilistic termination by monadic affine sized typing
- Probabilistic termination of CHRiSM programs
- Probabilistic termination versus fair termination
- Probabilistic termination: soundness, completeness, and compositionality
- Probability theory. A comprehensive course.
- Recursive Predicates and Quantifiers
- Recursively enumerable sets of positive integers and their decision problems
- Semantics of probabilistic programs
- Term Rewriting and Applications
- Termination analysis of probabilistic programs through Positivstellensatz's
- Termination of Probabilistic Concurrent Program
- Verification of Probabilistic Programs
- Weakest precondition reasoning for expected run-times of probabilistic programs
Cited in
(21)- Probabilistic termination versus fair termination
- Learning probabilistic termination proofs
- Latticed \(k\)-induction with an application to probabilistic programs
- Automatic Generation of Moment-Based Invariants for Prob-Solvable Loops
- On the hardness of almost-sure termination
- Weakest precondition reasoning for expected run-times of probabilistic programs
- Generating functions for probabilistic programs
- Densities of almost surely terminating probabilistic programs are differentiable almost everywhere
- Universal equivalence and majority of probabilistic programs over finite fields
- 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
- On probabilistic techniques for data flow analysis
- Probabilistic program verification via inductive synthesis of inductive invariants
- 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)