Google Groups no longer supports new Usenet posts or subscriptions. Historical content remains viewable.
Dismiss
AIB 2015-05: Inferring Lower Bounds for Runtime Complexity
3 views
Skip to first unread message
Thomas Ströder
Feb 14, 2015, 9:13:06 PM2/14/15
to
The following technical report is available from
http://aib.informatik.rwth-aachen.de:
Inferring Lower Bounds for Runtime Complexity
Florian Frohn, Jürgen Giesl, Jera Hensel, Cornelius Aschermann, and
Thomas Ströder
AIB 2015-05
We present the first approach to deduce lower bounds for innermost
runtime complexity of term rewrite systems (TRSs) automatically.
Inferring lower runtime bounds is useful to detect bugs and to
complement existing techniques that compute upper complexity bounds. The
key idea of our approach is to generate suitable families of rewrite
sequences of a TRS and to find a relation between the length of such a
rewrite sequence and the size of the first term in the sequence. We
implemented our approach in the tool AProVE and evaluated it by
extensive experiments.
http://aib.informatik.rwth-aachen.de:
Inferring Lower Bounds for Runtime Complexity
Florian Frohn, Jürgen Giesl, Jera Hensel, Cornelius Aschermann, and
Thomas Ströder
AIB 2015-05
We present the first approach to deduce lower bounds for innermost
runtime complexity of term rewrite systems (TRSs) automatically.
Inferring lower runtime bounds is useful to detect bugs and to
complement existing techniques that compute upper complexity bounds. The
key idea of our approach is to generate suitable families of rewrite
sequences of a TRS and to find a relation between the length of such a
rewrite sequence and the size of the first term in the sequence. We
implemented our approach in the tool AProVE and evaluated it by
extensive experiments.
0 new messages