Structural techniques in descriptive complexity
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 Ehre...
| Main Author: | |
|---|---|
| Other Authors: | |
| Format: | Thesis |
| Language: | English |
| Published: |
2022
|
| Subjects: |
| _version_ | 1797110944475643904 |
|---|---|
| author | Paine, T |
| author2 | Abramsky, S |
| author_facet | Abramsky, S Paine, T |
| author_sort | Paine, T |
| collection | OXFORD |
| description | 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. |
| first_indexed | 2024-03-07T08:01:42Z |
| format | Thesis |
| id | oxford-uuid:303066c5-88ef-4227-b33e-f354270889c4 |
| institution | University of Oxford |
| language | English |
| last_indexed | 2024-03-07T08:01:42Z |
| publishDate | 2022 |
| record_format | dspace |
| spelling | oxford-uuid:303066c5-88ef-4227-b33e-f354270889c42023-10-06T10:55:05ZStructural techniques in descriptive complexityThesishttp://purl.org/coar/resource_type/c_db06uuid:303066c5-88ef-4227-b33e-f354270889c4Descriptive ComplexityCategorical SemanticsFinite model theoryEnglishHyrax Deposit2022Paine, TAbramsky, SIn 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. |
| spellingShingle | Descriptive Complexity Categorical Semantics Finite model theory Paine, T Structural techniques in descriptive complexity |
| title | Structural techniques in descriptive complexity |
| title_full | Structural techniques in descriptive complexity |
| title_fullStr | Structural techniques in descriptive complexity |
| title_full_unstemmed | Structural techniques in descriptive complexity |
| title_short | Structural techniques in descriptive complexity |
| title_sort | structural techniques in descriptive complexity |
| topic | Descriptive Complexity Categorical Semantics Finite model theory |
| work_keys_str_mv | AT painet structuraltechniquesindescriptivecomplexity |