Automated Expected Amortised Cost Analysis of Probabilistic Data Structures

DOI10.1007/978-3-031-13188-2_4MaRDI QIDQ6487331zbMATH OpenFDO

Authors Lorenz Leutgeb, Georg Moser, Florian Zuleger

Publication date 7 December 2022

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.1007/978-3-031-13188-2_4

Mathematics Subject Classification ID

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

Recommendations

• ATLAS: automated amortised complexity analysis of self-adjusting data structures
• Type-based analysis of logarithmic amortised complexity
• A systematic analysis of splaying
• Randomized splay trees: Theoretical and experimental results.
• Amortized complexity verified

Cites work

• scientific article; zbMATH DE number 439891 (Why is no real title available?)
• scientific article; zbMATH DE number 54254 (Why is no real title available?)
• scientific article; zbMATH DE number 1234104 (Why is no real title available?)
• scientific article; zbMATH DE number 1305510 (Why is no real title available?)
• scientific article; zbMATH DE number 819814 (Why is no real title available?)
• A probabilistic PDL
• A systematic analysis of splaying
• ATLAS: automated amortised complexity analysis of self-adjusting data structures
• Amortized Computational Complexity
• Amortized complexity verified
• Automated recurrence analysis for almost-linear expected-runtime bounds
• Automated termination analysis of polynomial probabilistic programs
• Foundations of probabilistic programming
• Inferring expected runtimes of probabilistic integer programs using expected sizes
• On probabilistic term rewriting
• Probability and Computing
• Randomized binary search trees
• Randomized splay trees: Theoretical and experimental results.
• Ranking and repulsing supermartingales for reachability in probabilistic programs
• Self-adjusting binary search trees
• Semantics of probabilistic programs
• Term Rewriting and Applications
• Type-based analysis of logarithmic amortised complexity
• Types and programing languages
• Verified analysis of random binary tree structures
• Weakest precondition reasoning for expected runtimes of randomized algorithms

Cited in

(7)

• ATLAS: automated amortised complexity analysis of self-adjusting data structures
• Control-flow refinement for complexity analysis of probabilistic programs in \textsf{KoAT} (short paper)
• From innermost to full almost-sure termination of probabilistic term rewriting
• From innermost to full probabilistic term rewriting: almost-sure termination, complexity, and modularity
• Proving Almost-Sure Innermost Termination of Probabilistic Term Rewriting Using Dependency Pairs
• A random bag preserving product operation
• Type-based analysis of logarithmic amortised complexity

This page was built for publication: Automated Expected Amortised Cost Analysis of Probabilistic Data Structures

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