DROPS

Document

DOI: 10.4230/LIPIcs.RTA.2010.385

Modular Complexity Analysis via Relative Complexity

Authors: Harald Zankl and Martin Korp

Published in: LIPIcs, Volume 6, Proceedings of the 21st International Conference on Rewriting Techniques and Applications (2010)

Abstract

In this paper we introduce a modular framework which allows to infer (feasible) upper bounds on the (derivational) complexity of term rewrite systems by combining different criteria. All current investigations to analyze the derivational complexity are based on a single termination proof, possibly preceded by transformations. We prove that the modular framework is strictly more powerful than the conventional setting. Furthermore, the results have been implemented and experiments show significant gains in power.

Cite as

Harald Zankl and Martin Korp. Modular Complexity Analysis via Relative Complexity. In Proceedings of the 21st International Conference on Rewriting Techniques and Applications. Leibniz International Proceedings in Informatics (LIPIcs), Volume 6, pp. 385-400, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2010)

Copy BibTex To Clipboard

@InProceedings{zankl_et_al:LIPIcs.RTA.2010.385,
  author =	{Zankl, Harald and Korp, Martin},
  title =	{{Modular Complexity Analysis via Relative Complexity}},
  booktitle =	{Proceedings of the 21st International Conference on Rewriting Techniques and Applications},
  pages =	{385--400},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-18-7},
  ISSN =	{1868-8969},
  year =	{2010},
  volume =	{6},
  editor =	{Lynch, Christopher},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.RTA.2010.385},
  URN =		{urn:nbn:de:0030-drops-26659},
  doi =		{10.4230/LIPIcs.RTA.2010.385},
  annote =	{Keywords: Term rewriting, complexity analysis, relative complexity, derivation length}
}

Search Results

Documents authored by Korp, Martin

Modular Complexity Analysis via Relative Complexity

Abstract

Cite as

Thanks for your feedback!

Could not send message