The Implicit Computational Complexity of Imperative Programming Languages

Lars Kristiansen

November 2001


During the last decade Cook, Bellantoni, Leivant and others have developed the theory of implicit computational complexity, i.e. the theory of predicative recursion, tiered definition schemes, etcetera. We extend and modify this theory to work in a context of imperative programming languages, and characterise complexity classes like P, LINSPACE, PSPACE and the classes in the Grzegorczyk hiearchy. Our theoretical framework seems promising with respect to applications in engineering.

Available as PostScript, PDF, DVI.


Last modified: 2003-06-08 by webmaster.