Semantic Frameworks for Complexity

Douglas J Gurr

Abstract: This thesis extends denotational semantics to take account of the resource requirements of programs.

We describe the approach we have taken in modelling the resource requirements of programs, and motivate the definition of a monoid M of resource values. A connection is established with Moggi's categorical semantics of computations, and this connection is exploited to study complexity as a monad constructor.

A formal system, the lambda_{com}-calculus, for reasoning the resource requirements of programs is developed. Operational and denotational semantics are defined for this system, and we prove a correspondence theorem.

We show that Moggi's framework is not sufficiently general to capture all the examples of interest to us. Therefore, we define a new class of models based on the idea of an external datum. We investigate the relationship between these two approaches.

The new framework is used to investigate various concepts of importance in complexity theory and the analysis of algorithms. In particular, we show how to capture the notions of input measures, upper bounds on complexity and non-exact complexity.

Ph.D Thesis - price £8.50

LFCS report ECS-LFCS-91-130 (also published as CST-72-91)

Previous | Index | Next