### Complexity Analysis by Graph Rewriting

Martin Avanzini and Georg MoserProceedings of the 10th International Symposium on Functional and Logic Programming (FLOPS 2010), Lecture Notes in Computer Science 6009, pp. 257 – 271, 2010.

### Abstract

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.

### BibTeX

@inproceedings{MAGM-FLOPS10, author = "Martin Avanzini and Georg Moser", title = "Complexity Analysis by Graph Rewriting", booktitle = "Proceedings of the 10th International Symposium on Functional and Logic Programming", series = "Lecture Notes in Computer Science", volume = 6009, pages = "257--271", publisher = "Springer-Verlag", year = 2010 }