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 }