Linear, Polynomial or Exponential? Complexity Inference in Polynomial Time

DOI10.1007/978-3-540-69407-6_7zbMath1142.68369OpenAlexW1548801608MaRDI QIDQ3507419

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 complexitystatic program analysislinear time complexitypolynomial time complexity

Mathematics Subject Classification ID

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

Related Items (6)

Algorithmically broad languages for polynomial time and space ⋮ Closed-form upper bounds in static cost analysis ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Cost analysis of object-oriented bytecode programs

Cites Work

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

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