License: Creative Commons Attribution-NonCommercial-NoDerivs 3.0 Unported license (CC BY-NC-ND 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.RTA.2010.385
URN: urn:nbn:de:0030-drops-26659
URL: https://drops.dagstuhl.de/opus/volltexte/2010/2665/
Go to the corresponding LIPIcs Volume Portal


Zankl, Harald ; Korp, Martin

Modular Complexity Analysis via Relative Complexity

pdf-format:
10002.ZanklHarald.2665.pdf (0.2 MB)


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.

BibTeX - Entry

@InProceedings{zankl_et_al:LIPIcs:2010:2665,
  author =	{Harald Zankl and Martin Korp},
  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 =	{Christopher Lynch},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2010/2665},
  URN =		{urn:nbn:de:0030-drops-26659},
  doi =		{10.4230/LIPIcs.RTA.2010.385},
  annote =	{Keywords: Term rewriting, complexity analysis, relative complexity, derivation length}
}

Keywords: Term rewriting, complexity analysis, relative complexity, derivation length
Collection: Proceedings of the 21st International Conference on Rewriting Techniques and Applications
Issue Date: 2010
Date of publication: 06.07.2010


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