• AIB 2016-03: Lower Runtime Bounds for Integer Programs

    From Jera Hensel@21:1/5 to All on Wed Apr 13 18:49:33 2016
    The following technical report is available from http://aib.informatik.rwth-aachen.de:

    Lower Runtime Bounds for Integer Programs
    Florian Frohn, Matthias Naaf, Jera Hensel, Marc Brockschmidt, and Jürgen
    AIB 2016-03

    We present a technique to infer lower bounds on the worst-case runtime complexity of integer programs. To this end, we construct 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. We implemented our technique in our tool
    LoAT and show that it infers non-trivial lower bounds for a large number
    of examples.

    --- SoupGate-Win32 v1.05
    * Origin: fsxNet Usenet Gateway (21:1/5)