Certifying Polynomial Time and Linear/Polynomial Space for Imperative Programs

DOI10.1137/S0097539704445597zbMath1100.68035MaRDI QIDQ5470728

Karl-Heinz Niggl, Henning Wunderlich

Publication date: 1 June 2006

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

zbMATH Keywords

linear spacepolynomial timeproperty testingimplicit computational complexitypolynomial spacestatic program analysisimperative programming languages

Mathematics Subject Classification ID

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

Related Items (11)

A type-based complexity analysis of object oriented programs ⋮ Algorithmically broad languages for polynomial time and space ⋮ A Characterization of NC k by First Order Functional Programs ⋮ Linear, Polynomial or Exponential? Complexity Inference in Polynomial Time ⋮ Closed-form upper bounds in static cost analysis ⋮ Unnamed Item ⋮ Recursion Schemata for NC k ⋮ ON THE EDGE OF DECIDABILITY IN COMPLEXITY ANALYSIS OF LOOP PROGRAMS ⋮ Unnamed Item ⋮ Cost analysis of object-oriented bytecode programs ⋮ Implicit characterizations of FPTIME and NC revisited

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