ATLAS: automated amortised complexity analysis of self-adjusting data structures

DOI10.1007/978-3-030-81688-9_5MaRDI QIDQ832253zbMATH OpenOpenAlexFDO

Authors Lorenz Leutgeb, Georg Moser, Florian Zuleger

Publication date 25 March 2022

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.1007/978-3-030-81688-9_5

zbMATH Keywords

functional programmingautomationself-adjusting data structuresconstraint solvingamortised cost analysis

Mathematics Subject Classification ID

Data structures (68P05) Functional programming and lambda calculus (68N18)

Recommendations

• Type-based analysis of logarithmic amortised complexity
• Automated Expected Amortised Cost Analysis of Probabilistic Data Structures
• Amortized complexity verified
• Amortized complexity verified
• A systematic analysis of splaying

Cites work

• scientific article; zbMATH DE number 1617246 (Why is no real title available?)
• scientific article; zbMATH DE number 54254 (Why is no real title available?)
• A combination framework for complexity
• A linear potential function for pairing heaps
• A systematic analysis of splaying
• Amortised resource analysis and typed polynomial interpretations
• Amortized Computational Complexity
• Amortized complexity verified
• An overview of Ciao and its design philosophy
• Analysing the complexity of functional programs: higher-order meets first-order
• Analyzing program termination and complexity automatically with \textsf{AProVE}
• Automated Complexity Analysis Based on the Dependency Pair Method
• Automated amortised resource analysis for term rewrite systems
• Automatic type inference for amortised heap-space analysis
• Boolean lexicographic optimization: algorithms \& applications
• Closed-form upper bounds in static cost analysis
• Complexity and resource bound analysis of imperative programs using difference constraints
• Decidable inequalities over infinite trees
• Efficient Algorithms for Asymptotic Bounds on Termination Time in VASS
• From Shapes to Amortized Complexity
• Multivariate amortised resource analysis for term rewrite systems
• Multivariate amortized resource analysis
• Non-polynomial worst-case analysis of recursive programs
• Purely Functional Data Structures
• Runtime complexity analysis of logically constrained rewriting
• Self-adjusting binary search trees
• Size-Change Abstraction and Max-Plus Automata
• Static prediction of heap space usage for first-order functional programs
• The polynomial complexity of vector addition systems with states
• Towards automatic resource bound analysis for OCaml
• Type-based cost analysis for lazy functional languages
• Verifying Nonlinear Real Formulas Via Sums of Squares
• Verifying procedural programs via constrained rewriting induction

Cited in

(4)

• Automated Expected Amortised Cost Analysis of Probabilistic Data Structures
• Amortized complexity verified
• Amortized complexity verified
• Type-based analysis of logarithmic amortised complexity

Describes a project that uses

Uses Software

• z3
• TiML
• Amortized Complexity
• OptiMathSAT
• TcT

This page was built for publication: ATLAS: automated amortised complexity analysis of self-adjusting data structures

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q832253)