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

imperative programming languagesimplicit computational complexitylinear spacepolynomial spacepolynomial timeproperty testingstatic program analysis

Mathematics Subject Classification ID

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

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)

• Implicit characterizations of FPTIME and NC revisited
• A type-based complexity analysis of object oriented programs
• On the computational complexity of imperative programming languages
• 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
• A Characterization of NC k by First Order Functional Programs
• Linear, Polynomial or Exponential? Complexity Inference in Polynomial Time
• Recursion Schemata for NC k
• On the edge of decidability in complexity analysis of loop programs
• Tight polynomial bounds for loop programs in polynomial space
• Tight polynomial worst-case bounds for loop programs
• An imperative language characterizing PTIME algorithms
• Cost analysis of object-oriented bytecode programs

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)