Wolfram Kahl
SQRL Report No. 57
53 pages
Software Quality Research Laboratory
Department of Computing and Software
McMaster University
March 2010
These notes are a current snapshot of the development of the theory of collagories, which are defined essentially as “distributive allegories without zero morphisms” and named for their close relationship with the adhesive categories currently popular as a foundation for the categorical double-pushout approach to graph transformation.
We argue that, thanks to their relation-algebraic flavour, collagories provide a more accessible and more flexible setting. One contributing factor to this is that the universal characterisations of pushouts and pullbacks in categories can be replaced with the local characterisations of tabulations and co-tabulations in collagories.
We document accessibility by showing ways to construct collagories of semi-unary algebras, which allow natural representations in particular of graph structures, also with fixed label sets.
Via the local ordering on homsets, collagories have a simple 2-categorical structure, and we use this to show that co-tabulations are equivalent to lax colimits of difunctional morphisms, and co-tabulations arising from spans of mappings are equivalent to bipushouts, which satisfy stronger conditions than just pushouts of mappings.
Finally, we consider Van-Kampen squares, the central ingredient of the definition of adhesive categories, and obtain an interesting characterisation of Van-Kampen squares in collagories.
Relation-algebraic graph transformation, Collagories, Allegories, Pushout, Bicolimit, Difunctional, Adhesive categories