Go to page

Bibliographic Metadata

Amortized resource analysis for term rewrite systems / by Manuel Schneckenreither, MSc
AuthorSchneckenreither, Manuel
Thesis advisorMoser, Georg
PublishedInnsbruck, 17 July 2018
Descriptionvi, 61 Seiten
Institutional NoteUniversität Innsbruck, Masterarbeit, 2018
Date of SubmissionJuly 2018
Document typeMaster Thesis
Keywords (DE)analysis of algorithms / amortised complexity / term rewriting / types / automation / worst-case / best-case
URNurn:nbn:at:at-ubi:1-23885 Persistent Identifier (URN)
 The work is publicly available
Amortized resource analysis for term rewrite systems [0.99 mb]
Abstract (English)

Based on earlier work on amortised resource analysis, we establish two novel automated amortised resource analyses for term rewrite systems. On one hand the worst-case analysis gives rise to polynomial bounds on the innermost runtime complexity of the analysed term rewrite system while on the other hand we present a best-case analysis for term rewrite systems. Both methods are presented in an inference system akin to a type system and build upon similar concepts. The worst-case analysis does not restrict the input rewrite system in any way, which facilitates integration in a general framework for resource analysis of programs. In contrast to that the best-case analysis is designed for first-order eagerly evaluated term rewrite systems and thus provides novel methods to fully automatically infer lower bounds. More precisely, we establish univariate amortised resource analyses based on the potential method which gives rise to polynomial bounds of the term rewrite system investigated. Due to the invocation of small-step semantics, the methods do not presuppose termination. This complements earlier work on automated amortised resource analysis. We have implemented the methods and provide ample evidence of their viability.

The PDF-Document has been downloaded 12 times.
CC-BY-SA-License (4.0)Creative Commons Attribution - ShareAlike 4.0 International License