Complexity, Graphs, and the Dependency Pair Method

Nao Hirokawa and Georg Moser

Proceedings of the 15th International Conference on Logic for Programming, Artificial Intelligence, and Reasoning (LPAR 2008), Lecture Notes in Artificial Intelligence 5330, pp. 652 – 666, 2008.


This paper builds on recent efforts (Hirokawa and Moser, 2008) 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.


  PDF |    doi:10.1007/978-3-540-89439-1_45  |  © Springer


author = "Nao Hirokawa and Georg Moser",
title = "Complexity, Graphs, and the Dependency Pair Method",
booktitle = "Proceedings of the 15th International Conferences on Logic for
Programming, Artificial Intelligence and Reasoning",
series = "Lecture Notes in Artificial Intelligence",
volume = 5330,
publisher = "Springer-Verlag",
year = 2008,
pages = "652--666"
Nach oben scrollen