Structural techniques in descriptive complexity

Thesis

In 2017, Abramsky, Dawar, and Wang published a paper which gave a comonadic characterisation of pebble games, tree-width, and k-variable logic, a key trio of related concepts in Finite Model Theory. In 2018, Abramsky and Shah expanded upon this to give an analogous comonadic characterisation of Ehrenfeucht Fraisse games, tree-depth, and bounded quantifier rank logic. A key feature of these papers is the connection between two previously distinct subfields of logic in computer science; Categorical Semantics, and Finite Model Theory. This thesis applies the ideas and techniques in these papers to give a categorical account of some cornerstone results of Finite Model Theory, including Rossman’s Equirank Homomorphism Preservation Theorem, Courcelle’s Theorem (on the model-checking properties of structures of bounded tree-width), and Gaifman’s Locality Theorem.

Authors: Paine, T

• DOI: 10.5287/ora-w44g4zmkd
• Type of award: DPhil
• Level of award: Doctoral
• Awarding institution: University of Oxford
• Language: English
• Keywords: finite quantifier rank; bounded tree-depth; locality; categorical semantics; finite Model theory; Courcelle's Theorem; descriptive complexity; homomorphism preservation Theorems; bounded tree-width; finite variable logic; Ehrenfeucht Fraisse games
• Subjects: Descriptive Complexity; Finite model theory; Categorical Semantics