Computing expected runtimes for constant probability programs
From MaRDI portal
Publication:2305420
DOI10.1007/978-3-030-29436-6_16OpenAlexW2969916489MaRDI QIDQ2305420
Peter Giesl, Jürgen Giesl, Marcel Hark
Publication date: 10 March 2020
Full work available at URL: https://arxiv.org/abs/1905.09544
Mechanization of proofs and logical operations (03B35) Theorem proving (automated and interactive theorem provers, deduction, resolution, etc.) (68V15)
Related Items (4)
Automated termination analysis of polynomial probabilistic programs ⋮ Inferring expected runtimes of probabilistic integer programs using expected sizes ⋮ Computing expected runtimes for constant probability programs ⋮ Generating functions for probabilistic programs
Uses Software
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- The solution of linear probabilistic recurrence relations
- Verified tail bounds for randomized programs
- Automated recurrence analysis for almost-linear expected-runtime bounds
- Analyzing probabilistic pushdown automata
- Termination of nondeterministic probabilistic programs
- Computing expected runtimes for constant probability programs
- Weakest Precondition Reasoning for Expected Run–Times of Probabilistic Programs
- Probabilistic Termination
- Algorithmic analysis of qualitative and quantitative termination problems for affine probabilistic programs
- One-Counter Stochastic Games
- On the Hardness of Almost–Sure Termination
- Minimizing Expected Termination Time in One-Counter Markov Decision Processes
- Probabilistic recurrence relations
- Abstraction, Refinement and Proof for Probabilistic Systems
- Computer Aided Verification
- On Termination of Integer Linear Loops
- Stochastic invariants for probabilistic termination
- Term Rewriting and Applications
- Termination of Integer Linear Programs
- Termination of triangular Integer loops is decidable
This page was built for publication: Computing expected runtimes for constant probability programs
