AIB 2011-03: A Dependency Pair Framework for Innermost Complexity Analysis of Term Rewrite Systems

The following technical report is available from http://aib.informatik.rwth-aachen.de:

A Dependency Pair Framework for Innermost Complexity Analysis of Term Rewrite Systems Lars Noschinski, Fabian Emmes, Jürgen Giesl AIB 2011-03

We present a modular framework to analyze the innermost runtime complexity of term rewrite systems automatically. Our method is based on the dependency pair framework for termination analysis. In contrast to previous work, we developed a direct adaptation of successful termination techniques from the dependency pair framework in order to use them for complexity analysis. By extensive experimental results, we demonstrate the power of our method compared to existing techniques.