Complexity Analysis by Graph Rewriting

Complexity Analysis by Graph Rewriting
M. Avanzini and G. Moser
Proceedings of the 10th International Symposium on Functional and Logic Programming, volume 6009 of Lecture Notes in Computer Science, pages 257–271, 2010.


Recently, many techniques have been introduced that allow the (automated) classification of the runtime complexity of term rewrite systems (TRSs for short). In this paper we show that polynomial (innermost) runtime complexity of TRSs induces polytime computability of the functions defined. In this way we show a tight correspondence between the number of steps performed in a given rewrite system and the computational complexity of an implementation of rewriting. The result uses graph rewriting as a first step towards the implementation of term rewriting. In particular, we prove the adequacy of (innermost) graph rewriting for (innermost) term rewriting.


Term Rewriting, Invariance, ICC, Graph Rewriting