Complexity Analysis by Rewriting

Martin Avanzini and Georg Moser

Proceedings of the 9th International Symposium on Functional and Logic Programming (FLOPS 2008), Lecture Notes in Computer Science 4989, pp. 130 – 146, 2008.


In this paper we introduce a restrictive version of the multiset path order, called polynomial path order. This recursive path order
induces polynomial bounds on the maximal number of innermost rewrite steps. This result opens the way to automatically verify for a given program, written in an eager functional programming language, that the maximal number of evaluation steps starting from any function call is polynomial in the input size. To test the feasibility of our approach we have implemented this technique and compare its applicability to existing methods.


  PDF |    doi:10.1007/978-3-540-78969-7_11  |  © Springer


author = "Martin Avanzini and Georg Moser",
title = "Complexity Analysis by Rewriting",
booktitle = "Proceedings of the 9th International Symposium on
Functional and Logic Programming",
series = "Lecture Notes in Computer Science",
volume = 4989,
publisher = "Springer-Verlag",
year = 2008,
pages = "130--146"
Nach oben scrollen