We argue that there is a link between implicit computational complexity theory and reversible computation. We introduce inherently reversible programming languages which capture the complexity classes etime and . Furthermore, we discuss and analyze higher-order versions of our reversible programming languages.

We prove that neat and natural fragments of the higher order programming language, PCF, capture complexity classes defined by imposing resource bounds on Turing machines. Moreover, we survey some related research on on Gödel’s T, and discuss the relationship between fragments of Gödel’s T and fragments of PCF. Our proofs are based on denotational semantics and domain theory.

We present a method for certifying that the values computed by an imperative program will be bounded by polynomials in the program's inputs. To this end, we introducemwp-matrices and define a semantic relation ⊧ C :M, where C is a program andMis anmwp-matrix. It follows straightforwardly from our definitions that there existsMsuch that ⊧ C :Mholds iff every value computed by C is bounded by a polynomial in the inputs. Furthermore, we provide a syntactical proof calculus and define the relation ⊢ C :Mto hold iff there exists a derivation in the calculus where C :Mis the bottom line. We prove that ⊢ C :Mimplies ⊧ C :M. By means of exhaustive proof search, an algorithm can decide if there existsMsuch that the relation ⊢ C :Mholds, and thus, our results yield a computational method.

Policy Based Management aims to constrain and even to determine the behaviour of computer systems that operate in dynamic environments, e.g. for the implementation of business goals. Autonomic computing supplements this with the aim to allow computer systems operate in a stable and predictable fashion with a minimum of human involvement. In this work we use a formulation of autonomic computing based on the cfengine model of convergent operations to discuss the computational cost of implementing autonomic regulation. By placing the autonomic properties of a system at a low level, but with a high degree of abstraction, we are able to make quite general statements about the computation cost of searching for autonomic policies.