Comonadic semantics for guarded fragments

Understand

In previous work, Abramsky, Dawar and Wang (LiCS 2017) and Abramsky and Shah (CSL 2018) have shown how a range of model comparison games which play a central role in finite model theory, including Ehrenfeucht-Fraisse, pebbling, and bisimulation games, can be captured in terms of resource-indexed comonads on the category of relational structures.

• Moreover, the coalgebras for these comonads capture important combinatorial parameters such as tree-width and tree-depth.
• The present paper extends this analysis to quantifier-guarded fragments of first-order logic.
• We give a systematic account, covering atomic, loose and clique guards.