Google Groups no longer supports new Usenet posts or subscriptions. Historical content remains viewable.
Dismiss
AIB 2016-03: Lower Runtime Bounds for Integer Programs
1 view
Skip to first unread message
Jera Hensel
Apr 13, 2016, 6:49:35 PM4/13/16
to
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
Giesl
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.
http://aib.informatik.rwth-aachen.de:
Lower Runtime Bounds for Integer Programs
Florian Frohn, Matthias Naaf, Jera Hensel, Marc Brockschmidt, and Jürgen
Giesl
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.
0 new messages