Adhesivity with Partial Maps instead of Spans

Issue title: Recent Developments in the Theory of Graph Transformation, 2010

Article type: Research Article

Authors: Heindel, Tobias

Affiliations: Institut CARNOT CEA LIST, DILS/LMEASI, Commissariat à l'énergie atomique et aux énergies alternatives, 91191 Gif sur Yvette CEDEX, France, tobias.heindel@cea.fr

Note: [] This work was partially supported by the EU Artemis project CHARTER and the ANR project COMPLICE.

Abstract: The introduction of adhesive categories revived interest in the study of properties of pushouts with respect to pullbacks that started over thirty years ago for the category of graphs. Adhesive categories – of which graphs are the “archetypal” example – are defined by a single property of pushouts along monos that implies essential lemmas and central theorems of double pushout rewriting such as the local Church-Rosser Theorem. The present paper shows that a strictly weaker condition on pushouts suffices to obtain essentially the same results: it suffices to require pushouts to be hereditary, i.e. they have to remain pushouts when they are embedded into the associated category of partial maps. This fact however is not the only reason to introduce partial map adhesive categories as categories with pushouts along monos (of a certain stable class) that are hereditary. There are two equally important motivations: first, there is an application relevant example category that cannot be captured by the more established variations of adhesive categories; second, partial map adhesive categories are “conceptually similar” to adhesive categories as the latter can be characterized as those categories with pushout along monos that remain bi-pushouts when they are embedded into the associated bi-category of spans. Thus, adhesivity with partial maps instead of spans appears to be a natural candidate for a general rewriting framework.

Keywords: graph transformation, category theory, adhesive categories, double pushout rewriting, single pushout rewriting

DOI: 10.3233/FI-2012-704

Journal: Fundamenta Informaticae, vol. 118, no. 1-2, pp. 1-33, 2012