Summary: This paper builds on recent efforts [N. Hirokawa and G. Moser, “Automated complexity analysis based on the dependency pair method”, Lect. Notes Comput. Sci. 5195, 364–379 (2008; Zbl 1165.68390)] to exploit the dependency pair method for verifying feasible, i.e., polynomial runtime complexities of term rewrite systems automatically. We extend our earlier results by revisiting dependency graphs in the context of complexity analysis. The obtained new results are easy to implement and considerably extend the analytic power of our existing methods. The gain in power is even more significant when compared to existing methods that directly, i.e., without the use of transformations, induce feasible runtime complexities. We provide ample numerical data for assessing the viability of the method.
For the entire collection see [Zbl 1154.68007].