Inferring Lower Runtime Bounds for Integer Programs

ACM Transactions on Programming Languages and Systems, vol. 42, pp. 1–50

Abstract

We present a technique to infer lower bounds on the worst-case runtime complexity of integer programs, where in contrast to earlier work, our approach is not restricted to tail-recursion. Our technique constructs symbolic representations of program executions using a framework for iterative, under-approximating program simplification. The core of this simplification is a method for (under-approximating) program acceleration based on recurrence solving and a variation of ranking functions. Afterwards, we deduce asymptotic lower bounds from the resulting simplified programs using a special-purpose calculus and an SMT encoding. We implemented our technique in our tool LoAT and show that it infers non-trivial lower bounds for a large class of examples.

Authors 4

1. Florian Frohn

   Max Planck Institute for Informatics

   Affiliation as printed

   Max Planck Institute for Informatics, Germany

   Max-Planck-Institute for Informatics, Germany

2. Matthias Naaf Aachen

   RWTH Aachen University

   Affiliation as printed

   RWTH Aachen University, Aachen, Germany

   RWTH Aachen, University, Aachen, Germany

3. Marc Brockschmidt

   Microsoft Research (United Kingdom)

   Affiliation as printed

   Microsoft Research, Cambridge, UK

   Microsoft Res., Cambridge, UK

4. Jürgen Giesl Aachen LuFG Informatik 2

   RWTH Aachen University

   Affiliation as printed

   LuFG Informatik 2, RWTH Aachen University, Aachen, Germany