1 citations · 1 across the 4 of their papers we have counts for
5 papers
KoAT: Automatic Complexity and Termination Analysis of Integer Programs
Nils Lommen, Éléanore Meyer, Jürgen Giesl
KoAT is a tool to automatically infer complexity bounds and prove termination of (possibly recursive) integer programs. To this end, KoAT implements an alternating modular inferenc…
Deciding Termination of Simple Randomized Loops
Éléanore Meyer, Jürgen Giesl
We show that universal positive almost sure termination (UPAST) is decidable for a class of simple randomized programs, i.e., it is decidable whether the expected runtime of such a…
Targeting Completeness: Automated Complexity Analysis of Integer Programs
Nils Lommen, Éléanore Meyer, Jürgen Giesl
There exist several approaches to infer runtime or resource bounds for integer programs automatically. In this paper, we study the subclass of periodic rational solvable loops (prs…
Control-Flow Refinement for Complexity Analysis of Probabilistic Programs in KoAT
Nils Lommen, Éléanore Meyer, Jürgen Giesl
Recently, we showed how to use control-flow refinement (CFR) to improve automatic complexity analysis of integer programs. While up to now CFR was limited to classical programs, in…
Automated Complexity Analysis of Integer Programs via Triangular Weakly Non-Linear Loops (Short WST Version)
Nils Lommen, Eleanore Meyer, Jürgen Giesl
There exist several results on deciding termination and computing runtime bounds for triangular weakly non-linear loops (twn-loops). We show how to use results on such subclasses o…