Amortized complexity verified
From MaRDI portal
Publication:2945642
DOI10.1007/978-3-319-22102-1_21zbMATH Open1465.68059OpenAlexW2406041226MaRDI QIDQ2945642FDOQ2945642
Authors: Tobias Nipkow 
Publication date: 14 September 2015
Published in: Interactive Theorem Proving (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/978-3-319-22102-1_21
Recommendations
- Amortized complexity verified
- scientific article; zbMATH DE number 54254
- ATLAS: automated amortised complexity analysis of self-adjusting data structures
- Type-based analysis of logarithmic amortised complexity
- Machine-checked verification of the correctness and amortized complexity of an efficient union-find implementation
Data structures (68P05) Functional programming and lambda calculus (68N18) Formalization of mathematics in connection with theorem provers (68V20)
Cites Work
- Title not available (Why is that?)
- Self-adjusting binary search trees
- Verifying Nonlinear Real Formulas Via Sums of Squares
- Self-Adjusting Heaps
- The derivation of a tighter bound for top-down skew heaps
- Machine-checked verification of the correctness and amortized complexity of an efficient union-find implementation
- The pairing heap: A new form of self-adjusting heap
- Purely Functional Data Structures
- Parallel reductions in \(\lambda\)-calculus
- Amortized Computational Complexity
- A systematic analysis of splaying
- Static prediction of heap space usage for first-order functional programs
Cited In (14)
- Title not available (Why is that?)
- ATLAS: automated amortised complexity analysis of self-adjusting data structures
- Automatic functional correctness proofs for functional search trees
- Title not available (Why is that?)
- Machine-checked verification of the correctness and amortized complexity of an efficient union-find implementation
- Verified analysis of random binary tree structures
- Amortized Complexity
- Automated Expected Amortised Cost Analysis of Probabilistic Data Structures
- Verified Root-Balanced Trees
- Amortized complexity verified
- Verifying the correctness and amortized complexity of a union-find implementation in separation logic with time credits
- Type-based analysis of logarithmic amortised complexity
- Formalizing network flow algorithms: a refinement approach in Isabelle/HOL
- Amortized Computational Complexity
Uses Software
This page was built for publication: Amortized complexity verified
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2945642)
