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