Certifying Polynomial Time and Linear/Polynomial Space for Imperative Programs

DOI10.1137/S0097539704445597MaRDI QIDQ5470728zbMATH OpenFDO

Authors Karl-Heinz Niggl, Henning Wunderlich

Publication date 1 June 2006

Published in SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/S0097539704445597

zbMATH Keywords

implicit computational complexitylinear spacepolynomial spacepolynomial timeproperty testingstatic program analysisimperative programming languages

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Mathematical aspects of software engineering (specification, verification, metrics, requirements, etc.) (68N30) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Specification and verification (program logics, model checking, etc.) (68Q60) Complexity of computation (including implicit computational complexity) (03D15)

Recommendations

• A flow calculus of \(mwp\)-bounds for complexity analysis
• On the computational complexity of imperative programming languages
• scientific article; zbMATH DE number 2084367
• scientific article; zbMATH DE number 1696756
• Linear, Polynomial or Exponential? Complexity Inference in Polynomial Time

Cited in

(14)

• A flow calculus of \(mwp\)-bounds for complexity analysis
• Closed-form upper bounds in static cost analysis
• Linear, Polynomial or Exponential? Complexity Inference in Polynomial Time
• On the edge of decidability in complexity analysis of loop programs
• scientific article; zbMATH DE number 7471667 (Why is no real title available?)
• scientific article; zbMATH DE number 7215283 (Why is no real title available?)
• A Characterization of NC k by First Order Functional Programs
• A type-based complexity analysis of object oriented programs
• Algorithmically broad languages for polynomial time and space
• Implicit characterizations of FPTIME and NC revisited
• Cost analysis of object-oriented bytecode programs
• Recursion Schemata for NC k
• On the computational complexity of imperative programming languages
• An imperative language characterizing PTIME algorithms

This page was built for publication: Certifying Polynomial Time and Linear/Polynomial Space for Imperative Programs

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