2026-08-16T12:03:42Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:5167 2024-03-06T10:36:11Z ddc:004 open_access

Multivariate Amortised Resource Analysis for Term Rewrite Systems Hofmann, Martin Moser, Georg program analysis,amortised analysis term rewriting,multivariate bounds We study amortised resource analysis in the context of term rewrite systems. We introduce a novel amortised analysis based on the potential method. The method is represented in an inference system akin to a type system and gives rise to polynomial bounds on the innermost runtime complexity of the analysed rewrite system. The crucial feature of the inference system is the admittance of multivariate bounds in the context of arbitrary data structures in a completely uniform way. This extends our earlier univariate resource analysis of typed term rewrite systems and continues our program of applying automated amortised resource analysis to rewriting. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Martin Hofmann and Georg Moser 2015 Is Part Of LIPIcs, Volume 38, 13th International Conference on Typed Lambda Calculi and Applications (TLCA 2015) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.TLCA.2015.241 urn:nbn:de:0030-drops-51675 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.TLCA.2015.241 eng https://creativecommons.org/licenses/by/3.0/legalcode