Automated higher-order complexity analysis

DOI10.1016/j.tcs.2003.10.022zbMath1071.68029MaRDI 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 mathematics; Program synthesis; Computational complexity analysis; Functional programs; Higher-order complexity

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

68N18: Functional programming and lambda calculus

Related Items

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

Uses Software

• Nuprl
• ACE

Cites Work

• 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
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item