Relating Structure and Power: Comonadic Semantics for Computational Resources

Understand

Combinatorial games are widely used in finite model theory, constraint satisfaction, modal logic and concurrency theory to characterize logical equivalences between structures.

• In particular, Ehrenfeucht-Fraisse games, pebble games, and bisimulation games play a central role.
• We show how each of these types of games can be described in terms of an indexed family of comonads on the category of relational structures and homomorphisms.
• The index k is a resource parameter which bounds the degree of access to the underlying structure.