  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. The coKleisli categories for these comonads can be used to give
syntax-free characterizations of a wide range of important logical
equivalences. Moreover, the coalgebras for these indexed comonads can be used
to characterize key combinatorial parameters: tree-depth for the
Ehrenfeucht-Fraisse comonad, tree-width for the pebbling comonad, and
synchronization-tree depth for the modal unfolding comonad. These results pave
the way for systematic connections between two major branches of the field of
logic in computer science which hitherto have been almost disjoint: categorical
semantics, and finite and algorithmic model theory.
