Zur Seitenansicht
 

Titelaufnahme

Titel
Amortized resource analysis for term rewrite systems / by Manuel Schneckenreither, MSc
VerfasserSchneckenreither, Manuel
Betreuer / BetreuerinnenMoser, Georg
ErschienenInnsbruck, 17 July 2018
Umfangvi, 61 Seiten
HochschulschriftUniversität Innsbruck, Masterarbeit, 2018
Datum der AbgabeJuli 2018
SpracheEnglisch
DokumenttypMasterarbeit
Schlagwörter (DE)analysis of algorithms / amortised complexity / term rewriting / types / automation / worst-case / best-case
URNurn:nbn:at:at-ubi:1-23885 Persistent Identifier (URN)
Zugriffsbeschränkung
 Das Werk ist frei verfügbar
Dateien
Amortized resource analysis for term rewrite systems [0.99 mb]
Links
Nachweis
Klassifikation
Zusammenfassung (Englisch)

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.

Statistik
Das PDF-Dokument wurde 11 mal heruntergeladen.
Lizenz
CC-BY-SA-Lizenz (4.0)Creative Commons Namensnennung - Weitergabe unter gleichen Bedingungen 4.0 International Lizenz