Complexity Analysis by Graph Rewriting

Martin Avanzini and Georg Moser

Proceedings of the 10th International Symposium on Functional and Logic Programming (FLOPS 2010), Lecture Notes in Computer Science 6009, pp. 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.


  PDF |    doi:10.1007/978-3-642-12251-4_19  |  © Springer


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
Nach oben scrollen