Lightweight semiformal time complexity analysis for purely functional data structures

DOI10.1145/1328438.1328457MaRDI QIDQ3189833zbMATH OpenOpenAlexFDO

Authors 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

amortised time complexitydependent typeslazy evaluationpurely functional data structures

Mathematics Subject Classification ID

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

Recommendations

• scientific article; zbMATH DE number 177794
• Type-based cost analysis for lazy functional languages
• Purely Functional Data Structures
• The role of lazy evaluation in amortized data structures
• Amortized complexity verified

Cited in

(15)

• Implicit computational complexity of subrecursive definitions and applications to cryptographic proofs
• Type-based cost analysis for lazy functional languages
• A Coq library for internal verification of running-times
• A Note on the Space Complexity of Fast D-Finite Function Evaluation
• Machine-checked verification of the correctness and amortized complexity of an efficient union-find implementation
• Relational cost analysis in a functional-imperative setting
• Verified Root-Balanced Trees
• Denotational semantics as a foundation for cost recurrence extraction for functional languages
• scientific article; zbMATH DE number 7204445 (Why is no real title available?)
• scientific article; zbMATH DE number 7649967 (Why is no real title available?)
• Verifying the correctness and amortized complexity of a union-find implementation in separation logic with time credits
• Amortized complexity verified
• Typable fragments of polynomial automatic amortized resource analysis
• Weighted rewriting
• Worst-case input generation for concurrent programs under non-monotone resource metrics

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

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