License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.RTA.2015.334
URN: urn:nbn:de:0030-drops-52068
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2015/5206/
Go to the corresponding LIPIcs Volume Portal

Frohn, Florian ; Giesl, Jürgen ; Hensel, Jera ; Aschermann, Cornelius ; Ströder, Thomas

Inferring Lower Bounds for Runtime Complexity

pdf-format:
26.pdf (0.7 MB)

Abstract

We present the first approach to deduce lower bounds for innermost runtime complexity of term rewrite systems (TRSs) automatically. Inferring lower runtime bounds is useful to detect bugs and to complement existing techniques that compute upper complexity
bounds. The key idea of our approach is to generate suitable families of rewrite sequences of a TRS and to find a relation between the length of such a rewrite sequence and the size of the first term in the sequence. We implemented our approach in
the tool AProVE and evaluated it by extensive experiments.

BibTeX - Entry

@InProceedings{frohn_et_al:LIPIcs:2015:5206,
  author =	{Florian Frohn and J{\"u}rgen Giesl and Jera Hensel and Cornelius Aschermann and Thomas Str{\"o}der},
  title =	{{Inferring Lower Bounds for Runtime Complexity}},
  booktitle =	{26th International Conference on Rewriting Techniques and Applications (RTA 2015)},
  pages =	{334--349},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-85-9},
  ISSN =	{1868-8969},
  year =	{2015},
  volume =	{36},
  editor =	{Maribel Fern{\'a}ndez},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2015/5206},
  URN =		{urn:nbn:de:0030-drops-52068},
  doi =		{10.4230/LIPIcs.RTA.2015.334},
  annote =	{Keywords: Term Rewriting, Runtime Complexity, Lower Bounds, Induction}
}

Keywords: Term Rewriting, Runtime Complexity, Lower Bounds, Induction
Collection: 26th International Conference on Rewriting Techniques and Applications (RTA 2015)
Issue Date: 2015
Date of publication: 18.06.2015

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI