| Summary: | 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.
|
|---|