License
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.RTA.2013.55
URN: urn:nbn:de:0030-drops-40534
URL: http://drops.dagstuhl.de/opus/volltexte/2013/4053/
Go to the corresponding LIPIcs Volume Portal


Avanzini, Martin ; Moser, Georg

A Combination Framework for Complexity

pdf-format:
6.pdf (0.7 MB)


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 - Entry

@InProceedings{avanzini_et_al:LIPIcs:2013:4053,
  author =	{Martin Avanzini and Georg Moser},
  title =	{{A Combination Framework for Complexity}},
  booktitle =	{24th International Conference on Rewriting Techniques and Applications (RTA 2013)},
  pages =	{55--70},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-53-8},
  ISSN =	{1868-8969},
  year =	{2013},
  volume =	{21},
  editor =	{Femke van Raamsdonk},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2013/4053},
  URN =		{urn:nbn:de:0030-drops-40534},
  doi =		{10.4230/LIPIcs.RTA.2013.55},
  annote =	{Keywords: program analysis, term rewriting, complexity analysis, automation}
}

Keywords: program analysis, term rewriting, complexity analysis, automation
Seminar: 24th International Conference on Rewriting Techniques and Applications (RTA 2013)
Issue Date: 2013
Date of publication: 14.06.2013


DROPS-Home | Fulltext Search | Imprint Published by LZI