Game comonads and beyond: compositional constructions for logic and algorithms

Game comonads represent a rare application of category theoretic methods to the fields of finite model theory and descriptive complexity. First introduced by Abramsky, Dawar and Wang in 2017, these new constructions exposed connections between Spoiler-Duplicator games used in logic, related algorithms for constraint satisfaction and structure isomorphism, and well-known parameters such as treewidth and treedepth. The compositional framework for logical resources emerging from these comonads has proved an important tool in generalising results from finite model theory and new game comonads have been invented for a range of different logics and algorithms. However, this framework has previously been limited by its inability to express logics which are strictly stronger than those captured by Abramsky, Dawar and Wang's pebbling comonad, $\mathbb{P}$_*k*. In this thesis, we show for the first time how to overcome these limitations by extending the reach of compositional techniques for logic and algorithms in a number of directions. Firstly, we deepen our understanding of the comonad $\mathbb{P}$_*k*, which previously captured the strongest logic of any game comonad. Doing so, we reveal new connections between the Kleisli category of $\mathbb{P}$_*k* and *k*-variable logics extended with different forms of quantification, including limited counting quantifiers and unary generalised quantifiers. Secondly, we show how to construct a new family of game comonads $\mathbb{H}$_*n,k* which capture logics extended by generalised quantifiers of all arities. This construction leads to new variants of Hella's *k*-pebble *n*-bijective game, new structural parameters generalising treewidth, and new techniques for constructing game comonads. Finally, we expand the realm of compositional methods in finite model theory beyond comonads, introducing new constructions on relational structures based on other aspects of category theory. In the first instance, we show that lifting well-known linear-algebraic monads on Set to the category of relational structures gives a compositional semantics to linear programming approximations of homomorphism and an elegant framework for studying these techniques. Furthermore, we use presheaves to give a new semantics for pebble games and algorithms for constraint satisfaction and structure isomorphism. Building on analogous work in quantum contextuality, we use a common invariant based on cohomology to invent efficient algorithms for approximating homomorphism and isomorphism and prove that these are far more powerful than those currently captured by game comonads.

Name dc:type.qualificationname

Doctor of Philosophy (PhD)

Level dc:type.qualificationlevel

Doctoral

Grantor dc:publisher.institution

University of Cambridge

Year dc:date.issued

2022

Author dc:creator

• Connolly, Adam

Advisor dc:contributor.advisor

• Dawar, Anuj

• Algorithms
• Category Theory
• Descriptive Complexity Theory
• Finite Model Theory
• Logic
• Theoretical Computer Science

Licence

• https://apollo8-f-pro.lib.cam.ac.uk/bitstreams/482c16ed-341e-44c4-82a5-c12682f68f15/download
• https://www.rioxx.net/licenses/all-rights-reserved/

Language dc:language

eng

Author Identifier

0000-0002-3032-5514

OAI identifier oai:identifier

oai:www.repository.cam.ac.uk:1810/360982