2026-07-22T21:23:57Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:2665 2024-03-06T10:33:30Z ddc:004 open_access

Modular Complexity Analysis via Relative Complexity Zankl, Harald Korp, Martin Term rewriting complexity analysis relative complexity derivation length 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Harald Zankl and Martin Korp 2010 Is Part Of LIPIcs, Volume 6, Proceedings of the 21st International Conference on Rewriting Techniques and Applications (2010) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.RTA.2010.385 urn:nbn:de:0030-drops-26659 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.RTA.2010.385 eng https://creativecommons.org/licenses/by-nc-nd/3.0/legalcode