2011 | OriginalPaper | Chapter
A Dependency Pair Framework for Innermost Complexity Analysis of Term Rewrite Systems
Authors : Lars Noschinski, Fabian Emmes, Jürgen Giesl
Published in: Automated Deduction – CADE-23
Publisher: Springer Berlin Heidelberg
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
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.