Abstract

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.

BibTeX

@article{MAGM-IC2016,
title   = "A combination framework for complexity",
author  = "Martin Avanzini and Georg Moser",
journal = "Information and Computation",
volume  = 248,
pages   = "22-55",
year    = 2016
}