Complexity analysis by rewriting
Martin Avanzini, Georg Moser · 2008
Abstract. In this paper we introduce a restrictive version of the mul-tiset 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 pro-gram, 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 exist-ing methods. 1