Lightweight semiformal time complexity analysis for purely functional data structures

DOI10.1145/1328438.1328457zbMath1295.68060OpenAlexW1982529770MaRDI QIDQ3189833

Nils Anders Danielsson

Publication date: 12 September 2014

Published in: Proceedings of the 35th annual ACM SIGPLAN-SIGACT symposium on Principles of programming languages (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/1328438.1328457

zbMATH Keywords

lazy evaluationdependent typespurely functional data structuresamortised time complexity

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Functional programming and lambda calculus (68N18) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Data structures (68P05) Mathematical aspects of software engineering (specification, verification, metrics, requirements, etc.) (68N30)

Related Items (11)

Verified Root-Balanced Trees ⋮ Type-based cost analysis for lazy functional languages ⋮ Machine-Checked Verification of the Correctness and Amortized Complexity of an Efficient Union-Find Implementation ⋮ Denotational semantics as a foundation for cost recurrence extraction for functional languages ⋮ Unnamed Item ⋮ Verifying the correctness and amortized complexity of a union-find implementation in separation logic with time credits ⋮ Amortized complexity verified ⋮ A Coq Library for Internal Verification of Running-Times ⋮ Unnamed Item ⋮ Implicit computational complexity of subrecursive definitions and applications to cryptographic proofs ⋮ Relational cost analysis in a functional-imperative setting

This page was built for publication: Lightweight semiformal time complexity analysis for purely functional data structures