Title: ATLAS: Automated Amortised Complexity Analysis of Self-Adjusting Data Structures
Other Titles: Automatisierte Analyse der Amortisierten Komplexität von Selbst-modifzierenden Datenstrukturen
Language: English
Authors: Leutgeb, Lorenz 
Qualification level: Diploma
Advisor: Zuleger, Florian 
Issue Date: 2021
Number of Pages: 67
Qualification level: Diploma
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 automatedamortised 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.
Keywords: Amortised Complexity; Static Analysis; Self-Adjusting Data Structures
URI: https://doi.org/10.34726/hss.2021.91302
DOI: 10.34726/hss.2021.91302
Library ID: AC16225272
Organisation: E192 - Institut für Logic and Computation 
Publication Type: Thesis
Appears in Collections:Thesis

Files in this item:

Show full item record

Page view(s)

checked on Jun 20, 2021


checked on Jun 20, 2021

Google ScholarTM


Items in reposiTUm are protected by copyright, with all rights reserved, unless otherwise indicated.