  In this paper we establish an automated amortised resource analysis for term
rewrite systems. The method is presented in an annotated type system and gives
rise to polynomial bounds on the innermost runtime complexity of the analysed
term rewrite system. Our analysis does not restrict the input rewrite system in
any way so that rewrite systems may serve as abstractions of first-order,
eagerly evaluated functional programs over user-defined inductive data-types.
This facilitates integration in a general framework for resource analysis of
programs. In particular, we have implemented the method and integrated it into
our analysis tool TcT. Furthermore, we have coupled the established analysis
with a complexity reflecting transformation from pure OCaml programs. This
extends the provided analysis to a fully automated resource analysis of
higher-order functional programs.

Logic in Computer Science