An invitation to game comonads
<|reference_start|>An invitation to game comonads: Game comonads offer a categorical view of a number of model-comparison games central to model theory, such as pebble and Ehrenfeucht-Fra\"iss\'e games. Remarkably, the categories of coalgebras for these comonads capture preservation of several fragments of resource-bounded logics, such as (infinitary) first-order logic with n variables or bounded quantifier rank, and corresponding combinatorial parameters such as tree-width and tree-depth. In this way, game comonads provide a new bridge between categorical methods developed for semantics, and the combinatorial and algorithmic methods of resource-sensitive model theory.   We give an overview of this framework and outline some of its applications, including the study of homomorphism counting results in finite model theory, and of equi-resource homomorphism preservation theorems in logic using the axiomatic setting of arboreal categories. Finally, we describe some homotopical ideas that arise naturally in the context of game comonads.<|reference_end|>
@article{abramsky2024an,
    title={An invitation to game comonads},
    author={Samson Abramsky and Luca Reggio},
    journal={arXiv preprint arXiv:2407.00606},
    year={2024},
    archivePrefix={arXiv},
    eprint={2407.00606},
    primaryClass={cs.LO math.CT}
}