Syntactic Measures of Complexity

By: Bruce Edmonds
Date: 18th October 1999
Also CPM Report No.: 99-55

My doctoral thesis:
Edmonds, B. (1999). Syntactic Measures of Complexity. Doctoral Thesis, University of Manchester, Manchester, UK.


Abstract

This thesis analyses the conception and measurement of complexity and then applies it to some aspects of formal languages.

It starts with a review of the philosophy of modelling. It continues by considering some simple examples to establish intuitions about the common use of `complexity' and goes on to examine what complexity can usefully be attributed to as a property. It argues that it most useful as an attribute of the specification of a model. Some unsatisfactory accounts of complexity are discussed as motivation for the definition of complexity that is then suggested. Some other accounts of complexity are shown to be special cases of the one suggested here.

This approach is then applied to formal languages. A set of properties of analytic complexity are set-out. The set of measures which satisfy these properties is formally investigated. The cyclomatic number of a representation of expressions is put forward to model analytic complexity. In order to analyse shifts in complexity a formal device called syntactic structures is defined. This consists of layers of syntaxes, each with its own production rules which generate the contents of that layer. Each syntactic structure can use substitutions from lower such structures, so that collections of such structures can form hierarchies.

These approaches to are then applied to axiomatic and proof theoretic aspects of logic. Some potential methods of simplification are suggested. Finally some remarks are made about the philosophical applications of this approach.

The appendices include a survey of measures of complexity in the literature; a brief description of a software tool written to explore syntactic structures, two relevant papers on the application of these ideas to scientific modelling and economics, and an extensive bibliography.


What to read (if you insist)


Accessible: