2013/02/05 by Martin Avanzini, Avanzini, Martin, Georg Moser +1 · 2 citations
Computer Science · #Computational Complexity (cs.CC) #F.1.3 #F.3.2 #F.4.1 #F.4.2 #FOS: Computer and information sciences #Logic, programming, and type systems #Parallel Computing and Optimization Techniques #Software Engineering Research
paper · pdf · doi:10.48550/arxiv.1302.0973
openalex publication_date 2013/02/05 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
In this paper we present a combination framework for polynomial complexity analysis of term rewrite systems. The framework covers both derivational and runtime complexity analysis. 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. We employ the framework in the automated complexity tool TCT. TCT implements a majority of the techniques found in the literature, witnessing that our framework is general enough to capture a very brought setting.