47 citations · 48 across the 4 of their papers we have counts for
5 papers
Improving Automatic Complexity Analysis of Integer Programs
Jürgen Giesl, Nils Lommen, Marcel Hark +1
In earlier work, we developed an approach for automatic complexity analysis of integer programs, based on an alternating modular inference of upper runtime and size bounds for prog…
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…
Termination of Triangular Polynomial Loops
Marcel Hark, Florian Frohn, Jürgen Giesl
We consider the problem of proving termination for triangular weakly non-linear loops (twn-loops) over some ring like , , or . The…
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…
Aiming Low Is Harder -- Induction for Lower Bounds in Probabilistic Program Verification
Marcel Hark, Benjamin Lucien Kaminski, Jürgen Giesl +1
We present a new inductive rule for verifying lower bounds on expected values of random variables after execution of probabilistic loops as well as on their expected runtimes. Our…