cl-banner

A combination framework for complexity

Martin Avanzini and Georg Moser

Information and Computation 248, pp. 22 – 55, 2016.

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 decompo-sition, that in the dependency pair setting greatly increases modularity.

 

  PDF |    doi:10.1016/j.ic.2015.12.007  

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