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 space; polynomial time; property testing; implicit computational complexity; polynomial space; static program analysis; imperative programming languages

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

68Q60: Specification and verification (program logics, model checking, etc.)

03D15: Complexity of computation (including implicit computational complexity)

68Q15: Complexity classes (hierarchies, relations among complexity classes, etc.)

68N30: Mathematical aspects of software engineering (specification, verification, metrics, requirements, etc.)

Related Items

Unnamed Item, 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, A type-based complexity analysis of object oriented programs, Algorithmically broad languages for polynomial time and space, Closed-form upper bounds in static cost 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