2 papers
cs.LO2020
Inferring Expected Runtimes of Probabilistic Integer Programs Using Expected Sizes
Fabian Meyer, Marcel Hark, Jürgen Giesl
We present a novel modular approach to infer upper bounds on the expected runtime of probabilistic integer programs automatically. To this end, it computes bounds on the runtime of…
cs.LO2019
Computing Expected Runtimes for Constant Probability Programs
Jürgen Giesl, Peter Giesl, Marcel Hark
We introduce the class of constant probability (CP) programs and show that classical results from probability theory directly yield a simple decision procedure for (positive) almos…