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)

- 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 convenient.

Appendices 6 and 7 are available as reports 97-23 and 97-24

#### Downloads

- The complete theses [570.31 kB]
- Title, Contents, Abstract etc. [18.83 kB]
- Chapter 1 - Introduction [13.10 kB]
- Chapter 2 - Models and Modelling [47.58 kB]
- Chapter 3 - Problems and Properties [73.71 kB]
- Chapter 4 - A Definition of Complexity [32.31 kB]
- Chapter 5 - Applications of Complexity to Formal Languages [98.37 kB]
- Chapter 6 - Philosophical Applications [18.16 kB]
- Chapter 7 - Conclusion [5.52 kB]
- Appendix 1 - A Brief Overview of Some Existing Formulations of Complexity [60.13 kB]
- Appendix 2 - Longer Proofs [46.31 kB]
- Appendix 3 - A Formalisation of Syntactic Structure [21.67 kB]
- Appendix 4 - A Tool for Exploring Syntactic Structures [18.03 kB]
- Appendix 5 - A Comparison of Different Rankings of Logical Formulae [19.28 kB]
- References [64.57 kB]