Abstract

We define a pipeline of complexity preserving transformations from higher-order programs to term rewrite systems. This way, we can harness the tool support on rewrite systems for the automatic complexity analysis of higher-order programs. Experimental evidence shows the feasibility of this approach.

BibTeX

@InProceedings{ADM:2015a,
  author    = "Martin Avanzini and Ugo Dal Lago and Georg Moser",
  title     = "Higher-Order Complexity Analysis: Harnessing First-Order Tools",
  booktitle = "Proceedings of the 6th Workshop on Developments in Implicit
               Computational Complexity (DICE 2015)",
  year      = {2015},
}