Automated Implicit Computational Complexity Analysis (System Description)

Automated Implicit Computational Complexity Analysis (System Description)
M. Avanzini and G. Moser and A. Schnabl
Proceedings of the 4th International Joint Conference on Automated Reasoning, volume 5195 of Lecture Notes in Computer Science, pages 132-138, 2008.

Abstract

Recent studies have provided many characterisations of the class of polynomial time computable functions through term rewriting techniques. In this paper we describe a (command-line based) system that implements the majority of these techniques and present experimental findings to simplify comparisons.

Categories

Term Rewriting, Complexity Analysis, Path Orders, ICCT, Implicit Computational Complexity