|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||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 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|
Show full item record
Files in this item:
|Leutgeb Lorenz - 2021 - ATLAS Automated Amortised Complexity Analysis of...pdf||931.29 kB||Adobe PDF|
checked on Jun 20, 2021
checked on Jun 20, 2021
Items in reposiTUm are protected by copyright, with all rights reserved, unless otherwise indicated.