1 Search Results for "Frohn, Florian"


Document
Inferring Lower Bounds for Runtime Complexity

Authors: Florian Frohn, Jürgen Giesl, Jera Hensel, Cornelius Aschermann, and Thomas Ströder

Published in: LIPIcs, Volume 36, 26th International Conference on Rewriting Techniques and Applications (RTA 2015)


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.

Cite as

Florian Frohn, Jürgen Giesl, Jera Hensel, Cornelius Aschermann, and Thomas Ströder. Inferring Lower Bounds for Runtime Complexity. In 26th International Conference on Rewriting Techniques and Applications (RTA 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 36, pp. 334-349, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)


Copy BibTex To Clipboard

@InProceedings{frohn_et_al:LIPIcs.RTA.2015.334,
  author =	{Frohn, Florian and Giesl, J\"{u}rgen and Hensel, Jera and Aschermann, Cornelius and Str\"{o}der, Thomas},
  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 =	{Fern\'{a}ndez, Maribel},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.RTA.2015.334},
  URN =		{urn:nbn:de:0030-drops-52068},
  doi =		{10.4230/LIPIcs.RTA.2015.334},
  annote =	{Keywords: Term Rewriting, Runtime Complexity, Lower Bounds, Induction}
}
  • Refine by Author
  • 1 Aschermann, Cornelius
  • 1 Frohn, Florian
  • 1 Giesl, Jürgen
  • 1 Hensel, Jera
  • 1 Ströder, Thomas

  • Refine by Classification

  • Refine by Keyword
  • 1 Induction
  • 1 Lower Bounds
  • 1 Runtime Complexity
  • 1 Term Rewriting

  • Refine by Type
  • 1 document

  • Refine by Publication Year
  • 1 2015

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail