Jan Hoffmann and Martin Hofmann (2010)

# Amortized Resource Analysis with Polynomial Potential

In: ESOP, pp. 287-306.

In 2003, Hofmann and Jost introduced a type system that uses a potential-based amortized analysis to infer bounds on the resource consumption of (first-order) functional programs. This$~$ analysis has been successfully applied to many standard algorithms but is limited to bounds that are linear in the size of the input. Here we extend this system to polynomial resource$~$ bounds. An automatic amortized analysis is used to infer these bounds for functional programs without further annotations if a maximal degree for the bounding polynomials is given. The$~$ analysis is generic in the resource and can obtain good bounds on heap-space, stack-space and time usage.

Document Actions