<div class="csl-bib-body">
<div class="csl-entry">Leutgeb, L. (2021). <i>ATLAS: Automated amortised complexity analysis of self-adjusting data structures</i> [Diploma Thesis, Technische Universität Wien]. reposiTUm. https://doi.org/10.34726/hss.2021.91302</div>
</div>
-
dc.identifier.uri
https://doi.org/10.34726/hss.2021.91302
-
dc.identifier.uri
http://hdl.handle.net/20.500.12708/17721
-
dc.description
Abweichender Titel nach Übersetzung der Verfasserin/des Verfassers
-
dc.description.abstract
Being able to argue about the performance of self-adjusting data structures (such as splay trees) has been a main objective when Sleator and Tarjan introduced the notion of amortised complexity.Analysing these data structures requires sophisticated potential functions, which typically contain logarithmic expressions. Possibly for these reasons, and despite the recent progress in automated resource analysis, they have so far eluded automation. In this thesis, we report on the first fully automated amortised complexity analysis of self-adjusting data structures. We make the following contributions:1. We introduce a novel amortised resource analysis couched in a type-and-effect system. Our analysis is formulated in terms of the physicist’s method of amortised analysis, and is potential-based. The type system makes use of logarithmic potential functions and is the first such system to exhibit logarithmic amortised complexity. 2. We encode the search for concrete potential function coefficients as an optimisation problem over a suitable constraint system. Our target function steers the search towards coefficients that minimise the inferred amortised complexity. 3. Automation is achieved by using a linear constraint system in conjunction with suitable lemmata schemes that encapsulate the required non-linear facts about the logarithm. We discuss our choices that achieve a scalable analysis.4. We present our tool ATLAS and report on experimental results for splay trees, splay heaps and pairing heaps. We completely automatically infer complexity estimates that match previous results (obtained by sophisticated pen-and-paper proofs), and in some cases even infer better complexity estimates than previously published.
en
dc.language
English
-
dc.language.iso
en
-
dc.rights.uri
http://rightsstatements.org/vocab/InC/1.0/
-
dc.subject
Amortised Complexity
en
dc.subject
Static Analysis
en
dc.subject
Self-Adjusting Data Structures
en
dc.title
ATLAS: Automated amortised complexity analysis of self-adjusting data structures
en
dc.title.alternative
Automatisierte Analyse der Amortisierten Komplexität von Selbst-modifzierenden Datenstrukturen