My doctoral thesis:
Edmonds, B. (1999). Syntactic Measures of
Complexity.
Doctoral Thesis, University of Manchester, Manchester, UK.
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.
Accessible:
The Complete Thesis | all.pdf |
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 |