Automated higher-order complexity analysis

DOI10.1016/j.tcs.2003.10.022zbMath1071.68029OpenAlexW2135155734MaRDI QIDQ1827392

Ralph Benzinger

Publication date: 6 August 2004

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2003.10.022

zbMATH Keywords

Feasible mathematicsProgram synthesisComputational complexity analysisFunctional programsHigher-order complexity

Mathematics Subject Classification ID

Related Items (11)

Verified Root-Balanced Trees ⋮ Type-based cost analysis for lazy functional languages ⋮ Denotational semantics as a foundation for cost recurrence extraction for functional languages ⋮ Closed-form upper bounds in static cost analysis ⋮ Automatic Inference of Upper Bounds for Recurrence Relations in Cost Analysis ⋮ Linear dependent types in a call-by-value scenario ⋮ Amortized complexity verified ⋮ Mechanisation of the AKS algorithm ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Cost analysis of object-oriented bytecode programs

Uses Software

• Nuprl
• ACE

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A note on complexity measures for inductive classes in constructive type theory
• Higher type recursion, ramification and polynomial time
• Computational complexity via programming languages: Constant factors do matter
• Automated complexity analysis of Nuprl extracted programs
• Optimality and inefficiency
• Proofs as programs
• Mechanical program analysis
• A Naïve Time Analysis and its Theory of Cost Equivalence
• Intensional interpretations of functionals of finite type I

This page was built for publication: Automated higher-order complexity analysis