Dependency Pairs and Polynomial Path Orders
Proceedings of the 20th International Conference on Rewriting Techniques and Applications, volume 5595 of Lecture Notes in Computer Science, pages 48–62, 2009.
© Springer Verlag Heidelberg
Abstract
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.
Categories
Term Rewriting, Complexity Analysis, Runtime Complexity Analysis, Path Orders, Predicative Recursion, Automation