A Combination Framework for Complexity

Martin Avanzini and Georg Moser

Proceedings of the 24th International Conference on Rewriting Techniques and Applications (RTA 2013), Leibniz International Proceedings in Informatics 21, pp. 55 – 70, 2013.


In this paper we present a combination framework for the automated polynomial complexity analysis of term rewrite systems. The framework covers both derivational and runtime complexity analysis, and is employed as theoretical foundation in the automated complexity tool TCT. We present generalisations of powerful complexity techniques, notably a generalisation of complexity pairs and (weak) dependency pairs. Finally, we also present a novel technique, called dependency graph decomposi-tion, that in the dependency pair setting greatly increases modularity.


  PDF |    doi:10.4230/LIPIcs.RTA.2013.55  |  © Creative Commons License – NC – ND


author = "Martin Avanzini and Georg Moser",
title = "A Combination Framework for Complexity",
booktitle = "Proceedings of the 24th International Conference on Rewriting
Techniques and Applications",
editor = "Femke van Raamsdonk",
series = "Leibniz International Proceedings in Informatics",
volume = 21,
pages = "55--70",
year = 2013,
doi = "10.4230/LIPIcs.RTA.2013.55"
Nach oben scrollen