On the hardness of analyzing probabilistic programs
From MaRDI portal
Mathematical aspects of software engineering (specification, verification, metrics, requirements, etc.) (68N30) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Specification and verification (program logics, model checking, etc.) (68Q60) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87)
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
- A probabilistic PDL
- Abstraction, Refinement and Proof for Probabilistic Systems
- Algorithmic analysis of qualitative and quantitative termination problems for affine probabilistic programs
- Classical recursion theory. The theory of functions and sets of natural numbers.
- Classical recursion theory. Vol. II
- Computational Complexity of Probabilistic Turing Machines
- CONCUR 2005 – Concurrency Theory
- Conditioning in probabilistic programming
- 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?)
- 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
(24)- Inferring covariances for probabilistic programs
- Probabilistic termination versus fair termination
- Generating functions for probabilistic programs
- Densities of almost surely terminating probabilistic programs are differentiable almost everywhere
- Computing expected runtimes for constant probability programs
- Weakest precondition reasoning for expected run-times of probabilistic programs
- Algorithmic analysis of qualitative and quantitative termination problems for affine probabilistic programs
- On probabilistic techniques for data flow analysis
- On the hardness of almost-sure termination
- Automatic Generation of Moment-Based Invariants for Prob-Solvable Loops
- Deciding fast termination for probabilistic VASS with nondeterminism
- Analysis-aware defeaturing: Problem setting and a posteriori estimation
- Universal equivalence and majority of probabilistic programs over finite fields
- Program analysis is harder than verification: a computability perspective
- Symbolic computation in automated program reasoning
- Does a Program Yield the Right Distribution?
- Probabilistic program verification via inductive synthesis of inductive invariants
- On lexicographic proof rules for probabilistic termination
- Probabilistic unifying relations for modelling epistemic and aleatoric uncertainty: semantics and automated reasoning with theorem proving
- Probabilistic verification beyond context-freeness
- From innermost to full probabilistic term rewriting: almost-sure termination, complexity, and modularity
- Deciding termination of simple randomized loops
- Learning probabilistic termination proofs
- Latticed \(k\)-induction with an application to probabilistic programs
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)
