Linear, Polynomial or Exponential? Complexity Inference in Polynomial Time

DOI10.1007/978-3-540-69407-6_7MaRDI QIDQ3507419zbMATH OpenOpenAlexFDO

Authors Neil D. Jones, Lars Kristiansen, Amir M. Ben-Amram

Publication date 19 June 2008

Published in Logic and Theory of Algorithms (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-540-69407-6_7

zbMATH Keywords

implicit computational complexitylinear time complexitypolynomial time complexitystatic program analysis

Mathematics Subject Classification ID

Mathematical aspects of software engineering (specification, verification, metrics, requirements, etc.) (68N30) Analysis of algorithms and problem complexity (68Q25)

Recommendations

• A flow calculus of \(mwp\)-bounds for complexity analysis
• Static complexity analysis of higher order programs
• Certifying Polynomial Time and Linear/Polynomial Space for Imperative Programs
• SPEED: precise and efficient static estimation of program computational complexity
• Inferring program specifications in polynomial-time

Cites work

• A flow calculus of \(mwp\)-bounds for complexity analysis
• Certifying Polynomial Time and Linear/Polynomial Space for Imperative Programs
• New Computational Paradigms
• On the computational complexity of imperative programming languages

Cited in

(13)

• Algorithmically broad languages for polynomial time and space
• Closed-form upper bounds in static cost analysis
• A flow calculus of \(mwp\)-bounds for complexity analysis
• Is there a logic for polynomial time?
• On the edge of decidability in complexity analysis of loop programs
• Tight polynomial bounds for loop programs in polynomial space
• A tier-based typed programming language characterizing feasible functionals
• Tight polynomial worst-case bounds for loop programs
• Certifying Polynomial Time and Linear/Polynomial Space for Imperative Programs
• Targeting Completeness: Using Closed Forms for Size Bounds of Integer Programs
• Polynomial loops: beyond termination
• Targeting completeness: automated complexity analysis of integer programs
• Cost analysis of object-oriented bytecode programs

This page was built for publication: Linear, Polynomial or Exponential? Complexity Inference in Polynomial Time

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