2026-07-25T06:36:41Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:4053 2024-03-06T10:34:45Z ddc:004 open_access

A Combination Framework for Complexity Avanzini, Martin Moser, Georg program analysis term rewriting complexity analysis automation 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 decomposition, that in the dependency pair setting greatly increases modularity. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Martin Avanzini and Georg Moser 2013 Is Part Of LIPIcs, Volume 21, 24th International Conference on Rewriting Techniques and Applications (RTA 2013) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.RTA.2013.55 urn:nbn:de:0030-drops-40534 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.RTA.2013.55 eng https://creativecommons.org/licenses/by/3.0/legalcode