How to delete categorically -- two pushout complement constructions

DOI10.1016/J.JSC.2010.09.007MaRDI QIDQ631570zbMATH OpenOpenAlexFDO

Authors Benjamin Braatz, Ulrike Golas, Thomas Soboll

Publication date 14 March 2011

Published in Journal of Symbolic Computation (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.jsc.2010.09.007

double-pushout approach graph transformation initial pushout pushout complement quasi-coproduct complement

Limits and colimits (products, sums, directed limits, pushouts, fiber products, equalizers, kernels, ends and coends, etc.) (18A30) Grammars and rewriting systems (68Q42)

Review text

The problem to construct pushout complements is motivated by the double pushout approach (DPO-approach) for graph transformations introduced in the early 1970ies in computer science, in order to generalize rule based rewriting techniques from strings and trees to graphs. DPO-graph transformation consists of two pushouts in opposite directions. In order to apply a rule to a graph a specific gluing condition has to be satisfied, which allows to construct a pushout complement as first step and a pushout construction as second step. Since the DPO-approach of rewriting is not only relevant for ordinary graphs, but also for labelled, typed and attributed graphs as well as for different kinds of Petri nets it is interesting to analyze existence, construction and uniqueness of pushout complements in a general categorical setting. This was first done by \textit{Y. Kawahara} [Theor. Comput. Sci. 77, No.~3, 267--289 (1990; Zbl 0723.18004)] in the framework of toposes, and later by \textit{H. Ehrig} et al. [Fundamentals of algebraic graph transformation, Springer Verlag (2006; Zbl 1095.68047)] using the concept of initial pushouts. Actuall it was shown recently at ICGT 2010 that initial pushouts can be constructed by finite intersections in finitary \(M\)-adhesive categories. This construction can be applied to several variants of graphs, but not to simple graphs, i.e., graphs without parallel edges, are important for specific applications in computer sciences. This is the main motivation for the present paper, where two different pushout complement constructions are introduced, compared with each other and applied to different categories of graphs. The first construction is based on initial pushouts, where weak initial pushouts are used in the case of simple graphs. The second construction is based on quasi-coproduct complements, which have been studied in the theory of \textit{T. Soboll} [Categorical modeling of multiagent systems. Diss., Univ. Salzburg (2008)]. Altogether the paper is well-motivated and well-written with detailed proofs and examples.

Recommendations

Cites work

Cited in

(14)

This page was built for publication: How to delete categorically -- two pushout complement constructions

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q631570)