Dependency Pairs and Polynomial Path Orders

Dependency Pairs and Polynomial Path Orders
M. Avanzini and G.Moser
Proceedings of the 20th International Conference on Rewriting Techniques and Applications, volume 5595 of Lecture Notes in Computer Science, pages 48–62, 2009.


We show how polynomial path orders can be employed efficiently in conjunction with weak innermost dependency pairs to automatically certify the polynomial runtime complexity of term rewrite systems and the polytime computability of those functions computed by these rewrite systems. The established techniques have been implemented and we provide ample experimental data to assess the new method.


Term Rewriting, Complexity Analysis, Runtime Complexity Analysis, Path Orders, Predicative Recursion, Automation