Amortised Resource Analysis and Typed Polynomial Interpretations (extended version)

Martin Hofmann, Georg Moser

We introduce a novel resource analysis for typed term rewrite systems based on a potential-based type system. This type system gives rise to polynomial bounds on the innermost runt…