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

Abstract

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)

• Chapters 1, 2, 3, 4, 6, 7 provide a fairly accessible account regarding modelling and complexity.
• Appendix 1 is a survey and overview of many of the existing formulations of complexity.
• Chapter 5, Appendicies 2, 3 and 5 gives a technical application of the theory to formal languages.
• Appendicies 6 and 7 are papers that were included in the thesis but which can be accessed more convieniantly elsewhere (follow the links).
• If you wish to browse references about complexity then you may well find my on-line bibliography of complexity much more conveniant.

Accessible:

• As a whole (584Kb, 245 pages A4):

The Complete Thesis

all.pdf

• By Parts:

Title, Contents, Abstract etc.	intro.pdf
1 - Introduction	chap1.pdf
2 - Models and Modelling	chap2.pdf
3 - Problems and Properties	chap3.pdf
4 - A Definition of Complexity	chap4.pdf
5 - Applications of Complexity to Formal Languages	chap5.pdf
6 - Philosophical Applications	chap6.pdf
7 - Conclusion	chap7.pdf
Appendix 1 - A Brief Overview of Some Existing Formulations of Complexity	appen1.pdf
Appendix 2 - Longer Proofs	appen2.pdf
Appendix 3 - A Formalisation of Syntactic Structure	appen3.pdf
Appendix 4 - A Tool for Exploring Syntactic Structures	appen4.pdf
Appendix 5 - A Comparison of Different Rankings of Logical Formulae	appen5.pdf
Appendix 6 - Complexity and Scientific Modelling
Appendix 7 - Complexity and Economics
References	refs.pdf

| BE Home | Complexity Links | Other CPM Reports | CPM home page |