# Parallel Transformations as Colimits

Thierry Boy de la Tour

► To cite this version:

Thierry Boy de la Tour. Parallel Transformations as Colimits. 2026. hal-05528530v2

HAL Id: hal-05528530

https://hal.univ-grenoble-alpes.fr/hal-05528530v2

Preprint submitted on 3 Mar 2026

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons CC BY 4.0 - Attribution - International License
Parallel Transformations as Colimits

Thierry Boy de la Tour

CNRS and University Grenoble Alpes, LIG Lab. Grenoble, France
thierry.boy-de-la-tour@imag.fr

**Abstract.** Parallel transformations are easier to conceive as colimits in a category of non rule-based transformations of the objects of a category *C*, thus eliminating the necessity of constructing a parallel rule. A category of *replacements* in *C* is defined, and examples illustrate what can be achieved by taking coproducts and other colimits in this category, and different reasons why diagrams may not have colimits. A general result is proved that characterizes the existence of colimits of replacements and yields an algorithm to compute them, with minimal assumption on *C*.

# 1 Introduction

One important issue in Graph Transformation is to identify the cases where two consecutive transformations can be performed simultaneously, by a unique *parallel* transformation that yields the same output from the same input as the sequence. Since transformations are rule-based this requires to find a suitable rule that generates the required parallel transformation on a suitable matching.

But why should a parallel transformation be rule-based? It seems strange that a new rule is required while we already have rules (and matchings) in the given transformations. This new rule in itself does not make the parallel transformation correct, its mere existence is not a criterion expressing what it means for the parallel transformation to be correct with respect to the given transformations. Even in independent parallelism, requiring that the result of the parallel transformation should be the same as that of the sequence would be a weak correction criterion; a graph transformation is more than just a set-theoretic function.

The case is even worse when two transformations of the same graph overlap so as not to be independent, since then there is no common result to be reached. Amalgamation [17] offers a way of producing a rule for a parallel transformation, but this is not sufficient to produce a semantical link between its transformation and the given transformations.

Hence it seems that producing a parallel or amalgamated rule, or any rule at all, is not the safe way to perform parallelization correctly. Yet this seems indispensable since rule-based graph transformations can only be considered correct with respect to rules or rule systems.

It therefore seems necessary to conceive transformations *per se*, without reference to rules, which leaves us with the problem of defining a correction criterion. However, in parallelization we only need to define correctness of transformations
with respect to other transformations. What we need is to define the structure
of a transformation, and how such structure may be preserved from some trans-
formation to another one.

This of course is the realm of category Theory, where mathematical structures
are defined by morphisms and their products. A morphism of transformations
$m: t \to t'$ should mean that the structure of $t$ is preserved in $t'$. And then, the
parallelization of $t_1$ and $t_2$ consists in finding a transformation $t$ that preserves
the structures of both $t_1$ and $t_2$, hence a cospan $t_1 \to t \leftarrow t_2$. And in order to
get the minimal structure required by $t_1$ and $t_2$, and nothing more, then this
cospan should be a coproduct (i.e., should be initial for such cospans).

In Section 2 a notion of transformations called *replacements* is proposed,
their structure is explained and defined through morphisms called *subsump-
tions*. Section 3 illustrates the scope and limitations of colimits in categories
of replacements through examples. Section 4 is devoted to computing colimits
of particular diagrams, and Section 5 extends this result to general colimits.
Related and future work are discussed in Section 6.

## 2 Replacements and Subsumptions

Most graph transformations approaches can be understood as replacements of a
subgraph (determined by a matching of the left hand side of a rule) by another
subgraph (the right hand side of the rule). They differ mostly in the way the
matched subgraph is removed; there is no standard tool in category theory to
perform such an operation. But there is generally an intermediate graph that
is the result of this operation, together with a morphism towards the input
(identifying the parts of the input that are not removed). They also agree on
the way the right hand side is added to the intermediate graph: by means of a
pushout. This is the ultimate operation that allows to link the added subgraph
to the intermediate graph and hence to the preserved part of the input.

If we abstract away the notions of rules and matchings, that are not identical
in all approaches, we obtain a fairly general notion of replacement.

**Definition 1.** A replacement in $\mathcal{C}$ is a diagram<fnref n="1" /> $\varrho$ in $\mathcal{C}$ of the form

<figure><img src="image_2.png" /></figure>

where the square is a pushout. *G* is the input, *D* the context, *I* the interface, *E*
the extension and *H* the result or output of the replacement. These *C*-objects
(and the *C*-morphisms *d*, *i*...) depend on $\varrho$ and may be referred to as $\varrho G$, $\varrho d$... to
avoid possible ambiguities. A replacement $\varrho$ is linear if *d* is monic.

<footnote n="1">¹ All finite diagrams in *C*, i.e., functors from a finite category to *C*, will be denoted by lowercase greek letters.</footnote>
Replacements also allow for duplications of parts of $G$, in which case the replacement is non-linear. An item $x$ of $G$ (vertex, edge, label...) can be duplicated as $x_1, \dots, x_n$ in $D$, which is indicated by $d(x_1) = \dots = d(x_n) = x$. Besides, the pushout with the extension allows for mergings of items of $G$, when $e$ is not monic. Thus replacements achieve many kind of transformations in $C$.

In particular if $C$ has an initial object $\emptyset$ then to any pair $(G, H)$ can be associated a $C$-span $G \leftarrow \emptyset \to H$ and therefore a replacement (with identities for $i$ and $q$) in which the input $G$ is completely replaced by the output $H$.

In order to define replacements as mathematical structures, we need a notion of morphism between them. The natural choice is to identify the structure of a replacement as the items that they remove and the items that they add. In other words, we say that the structure of a replacement $\varrho$ is preserved in $\varrho'$ if everything that is removed in $\varrho$ is also removed in $\varrho'$, and everything that is added in $\varrho$ is also added in $\varrho'$.

Comparing what is added is easy through $C$-morphisms between interfaces and between extensions. But replacements have no explicit reference to the items they remove, only the results of removing are available as the contexts. These contexts can also be compared through a $C$-morphism, but this comparison is only meaningful in terms of removed items if they are obtained from the same input.

**Definition 2.** Given two replacements $\varrho$ and $\varrho'$ in $C$, a subsumption morphism $u : \varrho \to \varrho'$ is a triple $(u_1, u_2, u_3)$ of $C$-morphisms such that

<figure><img src="image_3.png" /></figure>

commutes, where $G$ denotes $\varrho G$, $G'$ denotes $\varrho' G$, etc. Let $u' : \varrho' \to \varrho''$ be a subsumption morphism composable with $u$, then it is obvious that their composite $u' \circ u := (u_1 \circ u'_1, u'_2 \circ u_2, u'_3 \circ u_3)$ is again a subsumption morphism, that this composition law is associative and that $1_\varrho := (1_D, 1_I, 1_E)$ is an identity subsumption morphism. The category of replacements in $C$ and subsumption morphisms is denoted $\text{Rpl}(C)$, and its full subcategory of linear replacements is denoted $\text{Rpl}^*(C)$. For any $C$-object $G$ we write $\text{Rpl}(G)$ (resp. $\text{Rpl}^*(G)$) the full subcategory of (reps. linear) replacements with input $G$.

Let $|C|$ be the discrete category with all $C$-objects and $\ln : \text{Rpl}(C) \to |C|$ be the obvious input functor such that $\ln \varrho := \varrho G$. Let $\text{ltf} : \text{Rpl}(C) \to C$, $\text{Ext} : \text{Rpl}(C) \to C$ be the functors with $\text{ltf} \varrho := \varrho I$, $\text{ltf} u := u_2$, $\text{Ext} \varrho := \varrho E$ and $\text{Ext} u := u_3$.

Since subsumptions $u : \varrho \to \varrho'$ do not induce any $C$-morphisms between the outputs $H$ and $H'$, there is no output functor from $\text{Rpl}(C)$ to $C$.

One may conceived replacements the other way round, by first pushing something into the input and only then removing a part of the result. This would result in, say, co-replacements as diagrams of the form
<figure><img src="image_4.png" /></figure>

The problem now would be to define a suitable notion of subsumption between co-replacements. We could as above compare the extensions by assuming a commutative square with $e$ and $e'$. Since these extend the same object $G$, we could also impose a morphism from the pushout $P$ to $P'$. Then in order to compare the deletions it seems that we need a contravariant morphism between the outputs, hence a commuting diagram of the form

<figure><img src="image_5.png" /></figure>

But this is not the intended structure. Indeed, if $P$ contains an item $x$ that is removed, i.e., that has no preimage by $d$, we ought to ensure that $u_3(x)$ has no preimage by $d'$. Yet it is possible that an item $y$ of $H'$ has $d'(y) = u_3(x)$ if $d(u_4(y)) \neq x$ (and then we have $u_3(d(u_4(y))) = u_3(x)$).

Besides, most algebraic approaches to graph transformations clearly yield replacements.

## 3 Parallel Replacements

Suppose we have two replacements $\varrho_1$ and $\varrho_2$ with the same input $G$, we would like to define a replacement $\varrho$ that embodies both replacements in one, that performs both replacements simultaneously. If the two replacements occur at disjoint places in $G$, this should certainly be possible: just remove everything that is removed either by $\varrho_1$ or $\varrho_2$, and then add everything that is added either by $\varrho_1$ or $\varrho_2$. We therefore require that $\varrho$ subsumes both $\varrho_1$ and $\varrho_2$. And since we do not need anything else to be removed or added than what is removed or added in $\varrho_1$ or $\varrho_2$, the replacement $\varrho$ should be subsumed by all replacements that subsume both $\varrho_1$ and $\varrho_2$. In other words, $\varrho$ is the coproduct of $\varrho_1$ and $\varrho_2$ in $\mathrm{Rpl}(G)$.

If the replacements are not disjoint (whatever this may mean in absence of matchings), what could prevent these removals and additions? A simple example illustrates an important feature of replacements.
**Example 1.** In the category **Set**, we consider the replacements $\varrho_1$ corresponding to the diagram

$$ \{x\} \leftarrow \emptyset \leftarrow \emptyset \rightarrow \emptyset $$

(with result $\emptyset$) and $\varrho_2$ corresponding to

$$ \{x\} \leftarrow \{x\} \leftarrow \{x\} \rightarrow \{x\} $$

where $x$ is any set. Assume there is a coproduct $\varrho$ with diagram

$$ \{x\} \leftarrow D \leftarrow I \rightarrow E $$

and subsumptions $u : \varrho_1 \rightarrow \varrho$ and $v : \varrho_2 \rightarrow \varrho$, then $u_1 : D \rightarrow \emptyset$ entails $D = \emptyset$ and thus $I = \emptyset$. But then $v_2 : \{x\} \rightarrow \emptyset$, which is impossible.

Hence in a replacement the items of $D$ are items of $G$ that are not removed since they also occur in $H$, but they may or may not occur in $I$ and this makes a difference in the structure of the replacement if not in its result. If they do occur in $I$ then they are necessary to the extension and therefore cannot be removed. Otherwise they are not necessary, they just happen to be preserved and only play an accessory rôle in the replacement. The items of $G$ that enable the replacement are those that are removed (that have no preimage by $d$) and those, disjoint from the removed items, that are necessary to the extension (that have a preimage by $d \circ i$).

Hence there is a conflict between two replacements if one removes an item that is necessary to the other. In such cases it is impossible to find a replacement that preserves the structures of both replacements, i.e., to find a sink from them. The next example shows that this still allows some amount of overlaps.

**Example 2.** In Conway's Game of Life [11] there is an infinite 2-dimensional grid of cells each associated with a state, either dead or alive (pictured as white and black respectively). In order to replace states by other states, we need to remove or add states and thus to have empty cells. This is easily represented by an "empty" state (pictured in gray) that we define as being smaller than the other two. The category $C$ of configurations is the set of functions from the grid to the set of states, ordered by the common extension of the order on states.

For the sake of simplicity we only consider a 3×3-grid and the transformations of the configuration $\Box$ according to the rules of the game. The top and bottom live cells die by isolation since they have only one neighbour, which yields the following two replacements.

$$ \varrho_1 = \boxed{\phantom{000}} \leftarrow \boxed{\phantom{000}} \leftarrow \boxed{\phantom{000}} \rightarrow \boxed{\phantom{000}} $$

$$ \varrho_2 = \boxed{\phantom{000}} \leftarrow \boxed{\phantom{000}} \leftarrow \boxed{\phantom{000}} \rightarrow \boxed{\phantom{000}} $$

The two middle left and right cells come to life by the birth rule since they have three neighbours.

$$ \varrho_3 = \boxed{\phantom{000}} \leftarrow \boxed{\phantom{000}} \leftarrow \boxed{\phantom{000}} \rightarrow \boxed{\phantom{000}} $$

$$ \varrho_4 = \boxed{\phantom{000}} \leftarrow \boxed{\phantom{000}} \leftarrow \boxed{\phantom{000}} \rightarrow \boxed{\phantom{000}} $$
In these replacements the interface is the empty grid (initial object of $\mathcal{C}$) since from one generation to the next no cell is protected from change. This means that there are no conflicts between these replacements. The reader can easily check that the replacement

<figure><img src="image_6.png" /></figure>

subsumes $\varrho_1, \dots, \varrho_4$ and that its result is $\Box$. It is well known that this result cannot be obtained by sequential applications of the rules, in any order. This is the reason why Conway insisted on the necessity of applying the rules simultaneously.

This example shows that the existence of coproducts strictly encompasses *parallel independence*, i.e., a property ensuring an equivalent sequence of transformations, well-studied in many approaches to graph transformations. This line of work will not be pursued here.

Conflicts are not the only obstacle to the existence of coproducts, an obvious problem arises depending on the properties of $\mathcal{C}$.

**Example 3.** With the category of Example 2, we consider two replacements (that have nothing to do with the Game of Life)

<figure><img src="image_7.png" /></figure>

that clearly do not conflict. Yet they do not have a coproduct since their extensions $\Box$ and $\Box$ do not have a coproduct (or least upper bound) in $\mathcal{C}$. Note that $\mathcal{C}$ do not have pushouts either, and for example there is no replacement corresponding to

<figure><img src="image_8.png" /></figure>

Hence the existence of colimits in $\mathrm{Rpl}(\mathcal{G})$ depend on their existence in $\mathcal{C}$, and also, as the reader has certainly guessed, on the existence of limits in $\mathcal{C}$.

A more subtle problem arises in case of ambiguity.

**Example 4.** In the category of directed graphs we consider the replacement $\varrho_1$ corresponding to the diagram

<figure><img src="image_9.png" /></figure>

that deletes a loop, makes two copies of the vertex of the input, and adds an arrow between them. We next consider the replacement $\varrho_2$

<figure><img src="image_10.png" /></figure>

that deletes a loop and adds another one. There are two possible replacements that subsume both replacements:
<figure><img src="image_11.png" /></figure>

and

<figure><img src="image_12.png" /></figure>

but none subsumes the other. They correspond to the two possible ways of applying the two replacements simultaneously.

The following example shows that parallelization can be enhanced by considering other colimits in $Rpl(G)$ than just coproducts.

*Example 5 (inspired by [16,10]).* In the category of undirected graphs we consider replacements $\varrho_1, \varrho_2$ corresponding to the diagrams

<figure><img src="image_13.png" /></figure>

and

<figure><img src="image_14.png" /></figure>

respectively, where the morphisms all preserve the named vertices. The coproduct $\gamma$ of $\varrho_1$ and $\varrho_2$ is the replacement with

<figure><img src="image_15.png" /></figure>

The reader can easily check that there are subsumptions $i_1: \varrho_1 \to \gamma$ and $i_2: \varrho_2 \to \gamma$. But we may want to merge the two middle vertices between A and
B into one, hence find a way to express that one vertex added by $\varrho_1$ and one
added by $\varrho_2$ are one and the same. To do this, we first analyze what $\varrho_1$ and $\varrho_2$
have in common. Clearly, they both remove the edge AB and both add a vertex
and edges from this vertex to A and B. This corresponds to the replacement $\varrho$
with diagram

<figure><img src="image_16.png" /></figure>

It is again easy to see that there are subsumptions $u_1 : \varrho \to \varrho_1$ and $u_2 : \varrho \to \varrho_2$. We can then merge the common parts of $\varrho_1$ and $\varrho_2$ in their simultaneous replacement by taking the pushout of $\varrho_1 \leftarrow \varrho \to \varrho_2$, that is the replacement $\pi$ with diagram

<figure><img src="image_17.png" /></figure>

and the two obvious subsumptions $v_1 : \varrho_1 \to \pi$ and $v_2 : \varrho_2 \to \pi$ such that
$v_1 \circ u_1 = v_2 \circ u_2$. Note that $i_1 \circ u_1 \neq i_2 \circ u_2$ and that there are two subsumptions
from $\pi$ to $\gamma$.

# 4 Colimits with Fixed Contexts

We have seen in Example 2 that we cannot generally assume the category $\mathcal{C}$ to be
cocomplete, hence colimits in $\mathrm{Rpl}(\mathcal{G})$ will explicitly depend on the existence of
some colimits in $\mathcal{C}$. Another problem is that, in order to construct replacements,
we need to find pushouts in $\mathcal{C}$ yet we cannot assume that $\mathcal{C}$ has pushouts. Instead
we will rely on a weaker assumption.

**Definition 3.** For any index category $\mathcal{J}$, a category $\mathcal{C}$ has effective $\mathcal{J}$-colimits if for every diagram $D : \mathcal{J} \to \mathcal{C}$, if there exists a natural sink for $D$ then $D$ has a colimit.

From now on we assume that $\mathcal{C}$ has effective $\mathcal{J}$-colimits for all finite $\mathcal{J}$ (hence in particular for pushouts), and that it has $\mathcal{J}$-limits for all finite non-empty $\mathcal{J}$. It is easy to see that this is the case in Example 2, i.e. if there is an upper bound
then there is a least upper bound, and there is always a greatest lower bound, except that there is no terminal object.

We first tackle the problem of colimits in a case where conflicts are obviously impossible, that is when all replacements remove exactly the same objects, hence when they all have the same context. We assume a finite category $\mathcal{J}$ and will consider the colimits of diagrams of replacements with input $G$ and indexed by $\mathcal{J}$. See [12] or [1] for general definitions.

**Definition 4.** For any $\mathcal{C}$-morphism $d : D \to G$, let $\mathrm{Rpl}(d)$ be the subcategory of $\mathrm{Rpl}(G)$ of replacements $\varrho$ such that $\varrho d = d$ and subsumptions $u$ such that $u_1 = 1_D$.

**Lemma 1.** For every $\mathrm{Rpl}(d)$-morphisms $u : \varrho \to \varrho'$ there exists a unique $\mathcal{C}$-morphism $h_u : \varrho H \to \varrho' H$ such that $h_u \circ \varrho p = \varrho' p$ and $h_u \circ \varrho q = \varrho' q \circ u_3$.

*Proof.* Consider the diagram

<figure><img src="image_18.png" /></figure>

By the commutation of the top, left and front faces we get $\varrho'q \circ u_3 \circ \varrho e = \varrho'p \circ \varrho i$, and the conclusion follows since the back face is a pushout. $\square$

**Corollary 1.** $h_{1_e} = 1_{\varrho H}$ and $h_{u' \circ u} = h_{u'} \circ h_u$ for all $u' : \varrho' \to \varrho''$.

*Proof.* $h_{1_e} = 1_{\varrho H}$ is obvious by unicity, since $(1_{\varrho})_3 = 1_{\varrho E}$. We have $h_{u'} \circ h_u \circ \varrho p = h_{u'} \circ \varrho' p = \varrho'' p$ and $h_{u'} \circ h_u \circ \varrho q = h_{u'} \circ \varrho' q \circ u_3 = \varrho'' q \circ (u' \circ u)_3$, hence by unicity $h_{u' \circ u} = h_{u'} \circ h_u$. $\square$

Hence there is an output functor from $\mathrm{Rpl}(d)$ to $\mathcal{C}$. However, we will need not just the colimit of outputs but also a $\mathcal{C}$-morphism from $D$ to this colimit. One possibility is to add the morphisms $p$ to the diagram, hence an initial object to $\mathcal{J}$, but the easiest solution is to work in the coslice category $D\backslash\mathcal{C}$. This is possible since $\varrho p$ and $\varrho' p$ are $D\backslash\mathcal{C}$-objects and we can see $h_u : \varrho p \to \varrho' p$ as a $D\backslash\mathcal{C}$-morphism.

**Definition 5.** Let $\mathrm{Res}_d : \mathrm{Rpl}(d) \to D\backslash\mathcal{C}$ be the functor defined by $\mathrm{Res}_d \varrho := \varrho p$ and $\mathrm{Res}_d u := h_u$ for all $\mathrm{Rpl}(d)$-morphism $u : \varrho \to \varrho'$.

We assume a diagram in $\mathrm{Rpl}(d)$, i.e., a functor $D' : \mathcal{J} \to \mathrm{Rpl}(d)$ with index category $\mathcal{J}$.

**Theorem 1.** $D'$ has a colimit iff $\mathrm{Itf} \circ D'$, $\mathrm{Ext} \circ D'$ and $\mathrm{Res}_d \circ D'$ have colimits.
Proof. Sufficient condition. Let $((x_j)_{j \in \mathcal{J}}, \vec{I})$, $((y_j)_{j \in \mathcal{J}}, \vec{E})$ and $((z_j)_{j \in \mathcal{J}}, \vec{p}: D \to \vec{H})$ be colimits of $\text{ltf} \circ \mathcal{D}'$, $\text{Ext} \circ \mathcal{D}'$ and $\text{Res}_d \circ \mathcal{D}'$ respectively. For every $\mathcal{J}$-morphism $f: j \to j'$, since $\mathcal{D}'$ $f$ is a subsumption from $\mathcal{D}'j$ to $\mathcal{D}'j'$ we have $1_D \circ (\mathcal{D}'j')i \circ (\mathcal{D}'f)_2 = (\mathcal{D}'j)i$ and $(\mathcal{D}'j')e \circ (\mathcal{D}'f)_2 = (\mathcal{D}'f)_3 \circ (\mathcal{D}'j)e$, hence $(\mathcal{D}'j')i \circ (\text{ltf} \circ \mathcal{D}')f = (\mathcal{D}'j)i$ and

$$y_{j'} \circ (\mathcal{D}'j')e \circ (\text{ltf} \circ \mathcal{D}')f = y_{j'} \circ (\text{Ext} \circ \mathcal{D}')f \circ (\mathcal{D}'j)e = y_j \circ (\mathcal{D}'j)e,$$

so that the sinks $((\mathcal{D}'j)i)_{j \in \mathcal{J}}, D)$ and $((y_j \circ (\mathcal{D}'j)e)_{j \in \mathcal{J}}, \vec{E})$ are both natural for $\text{ltf} \circ \mathcal{D}'$ and there exist a unique $\vec{i}: \vec{I} \to D$ and a unique $\vec{e}: \vec{I} \to \vec{E}$ such that $\vec{i} \circ x_j = (\mathcal{D}'j)i$ and $\vec{e} \circ x_j = y_j \circ (\mathcal{D}'j)e$ for all $\mathcal{J}$-object $j$. Similarly we have

$$ \begin{align*} z_{j'} \circ (\mathcal{D}'j')q \circ (\text{Ext} \circ \mathcal{D}')f &= z_{j'} \circ (\mathcal{D}'j')q \circ (\mathcal{D}'f)_3 \\ &= z_{j'} \circ (\text{Res}_d \circ \mathcal{D}')f \circ (\mathcal{D}'j)q \quad \text{by Lemma 1} \\ &= z_j \circ (\mathcal{D}'j)q \end{align*} $$

so that $((z_j \circ (\mathcal{D}'j)q)_{j \in \mathcal{J}}, \vec{H})$ is a natural sink for $\text{Ext} \circ \mathcal{D}'$ hence there exists a unique $\vec{q}: \vec{E} \to \vec{H}$ such that $\vec{q} \circ y_j = z_j \circ (\mathcal{D}'j)q$ for all $j$.

Now, we also see that

$$ \begin{align*} z_{j'} \circ (\mathcal{D}'j')(q \circ e) \circ (\text{ltf} \circ \mathcal{D}')f &= z_{j'} \circ (\mathcal{D}'j')q \circ (\text{Ext} \circ \mathcal{D}')f \circ (\mathcal{D}'j)e \\ &= z_j \circ (\mathcal{D}'j)(q \circ e) \end{align*} $$

so that $((z_j \circ (\mathcal{D}'j)(q \circ e))_{j \in \mathcal{J}}, \vec{H})$ is natural for $\text{ltf} \circ \mathcal{D}'$ hence there exists a unique $\vec{r}: \vec{I} \to \vec{H}$ such that $\vec{r} \circ x_j = z_j \circ (\mathcal{D}'j)(q \circ e)$ for all $j$. Since

$$\vec{q} \circ \vec{e} \circ x_j = \vec{q} \circ y_j \circ (\mathcal{D}'j)e = z_j \circ (\mathcal{D}'j)(q \circ e)$$

then $\vec{q} \circ \vec{e} = \vec{r}$, and since $z_j$ is a $D\backslash\mathcal{C}$-morphism from $(\text{Res}_d \circ \mathcal{D}')j = (\mathcal{D}'j)p$ to $\vec{p}$ then

$$\vec{p} \circ \vec{i} \circ x_j = \vec{p} \circ (\mathcal{D}'j)i = z_j \circ (\mathcal{D}'j)(p \circ i) = z_j \circ (\mathcal{D}'j)(q \circ e)$$

hence $\vec{p} \circ \vec{i} = \vec{q} \circ \vec{e}$.

Let $\gamma$ be the commuting diagram

<figure><img src="image_19.png" /></figure>

in $\mathcal{C}$. We now prove that this square is a pushout. Let $D \xrightarrow{p'} H' \leftarrow^{q'} \vec{E}$ be a cospan such that $p' \circ \vec{i} = q' \circ \vec{e}$, we thus have

$$p' \circ (\mathcal{D}'j)i = p' \circ \vec{i} \circ x_j = q' \circ \vec{e} \circ x_j = q' \circ y_j \circ (\mathcal{D}'j)e$$
and since $((D^j)p, (D^j)q)$ is a pushout of $((D^j)i, (D^j)e)$ then there exists a unique $\mathcal{C}$-morphism $h'_j : (D^j)H \to H'$ such that $h'_j \circ (D^j)q = q' \circ y_j$ and $h'_j \circ (D^j)p = p'$ (i.e. $h'_j : (D^j)p \to p'$ in $D\backslash \mathcal{C}$). For all $f : j \to j'$ and by Lemma 1 we have $h'_{j'} \circ (\mathrm{Res}_d \circ D')f \circ (D^j)p = h'_{j'} \circ (D^j)p = p'$ and

$$h'_{j'} \circ (\mathrm{Res}_d \circ D')f \circ (D^j)q = h'_{j'} \circ (D^j)q' \circ (D^j)f = q' \circ y_{j'} \circ (\mathrm{Ext} \circ D')f = q' \circ y_j$$

hence by unicity $h'_{j'} \circ (\mathrm{Res}_d \circ D')f = h'_{j'}$, so that the sink $((h'_{j'})_{j \in \mathcal{J}}$, $p'$) is natural for $\mathrm{Res}_d \circ D'$ and there exists a unique $D\backslash \mathcal{C}$-morphism $h' : \vec{p} \to p'$ such that $h' \circ z_j = h'_j$ for all $j$. In $\mathcal{C}$ we thus have a unique $h' : \vec{H} \to H'$ such that $h' \circ \vec{p} = p'$ and for all $j$

$$h' \circ \vec{q} \circ y_j = h' \circ z_j \circ (D^j)q = h'_{j'} \circ (D^j)q = q' \circ y_j$$

hence $h' \circ \vec{q} = q'$ since $(y_j)_{j \in \mathcal{J}}$ is an epi-sink.

We have proved so far that $\gamma$ is a replacement and that $(1_D, x_j, y_j)$ is a subsumption from $D^j$ to $\gamma$ for all $j$. For every $\mathcal{J}$-morphism $f : j \to j'$ we have

$$(1_D, x_{j'}, y_{j'}) \circ D^j f = (1_D, x_{j'} \circ (\mathrm{ltf} \circ D^j) f, y_{j'} \circ (\mathrm{Ext} \circ D^j) f) = (1_D, x_j, y_j)$$

hence $((1_D, x_j, y_j)_{j \in \mathcal{J}}$, $\gamma$) is a natural sink for $D^j$, and there only remains to prove that it is a colimit of $D^j$.

Let $((u^j)_{j \in \mathcal{J}}$, $\varrho$) be a natural sink for $D^j$, then obviously $((\mathrm{ltf} u^j)_{j \in \mathcal{J}}$, $\mathrm{ltf} \varrho$) and $((\mathrm{Ext} u^j)_{j \in \mathcal{J}}$, $\mathrm{Ext} \varrho$) are natural sinks for $\mathrm{ltf} \circ D^j$ and $\mathrm{Ext} \circ D^j$ respectively, hence there exist a unique $y : \vec{I} \to \varrho I$ and a unique $z : \vec{E} \to \varrho E$ such that $y \circ x_j = u_2^j$ and $z \circ y_j = u_3^j$, hence a unique $v := (1_D, y, z)$ such that $v \circ (1_D, x_j, y_j) = u^j$ for all $j$. Since $\varrho i \circ y \circ x_j = \varrho i \circ u_2^j = (D^j) i$ then by unicity $\vec{I} = \varrho i \circ y$. Besides, we have

$$z \circ \vec{e} \circ x_j = z \circ y_j \circ (D^j)e = u_3^j \circ (D^j)e = \varrho e \circ u_2^j = \varrho e \circ y \circ x_j$$

for all $j$ and since $(x_j)_{j \in \mathcal{J}}$ is an epi-sink then $z \circ \vec{e} = \varrho e \circ y$, and we have proved that $v$ is a subsumption from $\gamma$ to $\varrho$.

**Necessary condition.** If $D$ has a colimit then $\mathrm{ltf} \circ D^j$, $\mathrm{Ext} \circ D^j$ and $\mathrm{Res}_d \circ D^j$ have natural sinks hence colimits. $\square$

**Corollary 2.** If $\mathcal{C}$ has pushouts then $\mathrm{ltf} \circ D^j$, $\mathrm{Ext} \circ D^j$ have colimits iff $D^j$ has a colimit.

*Proof.* The colimit of $\mathrm{Res}_d \circ D^j$ is only used to construct $\vec{p}$, itself used to construct $\vec{q}$, hence we can dispense with this hypothesis by constructing $D \xrightarrow{\vec{p}} \vec{H} \xleftarrow{\vec{q}} \vec{E}$ as a pushout of $D \xleftarrow{\vec{I}} \vec{I} \xrightarrow{\vec{e}} \vec{E}$. $\square$

# 5 Coherence Systems and Colimits

We now consider the general case and assume a diagram $D : \mathcal{J} \to \mathrm{Rpl}(G)$. In order to get a morphism $d$ from the limit of the contexts to $G$ we use the same
trick as above and work in the slice category $\mathcal{C}\backslash\mathcal{G}$. This is possible since for all $\mathcal{J}$-morphism $f: j \to j'$, $\mathcal{D}f$ is a subsumption and therefore its first component $(\mathcal{D}f)_1$ can be seen as a $\mathcal{C}\backslash\mathcal{G}$-morphism from $(\mathcal{D}j')d$ to $(\mathcal{D}j)d$.

**Definition 6.** Let $\text{CTOR}: \text{Rpl}(\mathcal{G}) \to \mathcal{C}\backslash\mathcal{G}$ be the contravariant functor such that $\text{CTOR}\varrho := \varrho d$ and $\text{CTOR}u := u_1$ for all subsumption $u: \varrho \to \varrho'$.

A coherence system $c$ for $\mathcal{D}$ is a collection of natural sources $((\mathcal{D}k)(d \circ i), (c_j^k)_{j \in \mathcal{J}})$ for $\text{CTOR} \circ \mathcal{D}$, one for every $\mathcal{J}$-object $k$, such that $c_k^k = (\mathcal{D}k)i$ and $c_j^k = c_j^{k'} \circ (\mathcal{D}f)_2$ for all $\mathcal{J}$-morphism $f: k \to k'$ and all $\mathcal{J}$-object $j$.

$\mathcal{D}$ is coherent if it admits a coherence system.

**Example 6.** In Example 4 we see that there is exactly one morphism from $\varrho_1 I$ to $\varrho_2 D$, but two morphisms from $\varrho_2 I$ to $\varrho_1 D$. The commutation conditions being obvious, we get two coherence systems for the coproduct diagram $\{\varrho_1, \varrho_2\}$.

**Lemma 2.** To every natural sink $((u^j)_{j \in \mathcal{J}}, \varrho)$ for $\mathcal{D}$ corresponds a coherence system for $\mathcal{D}$.

*Proof.* By hypothesis the subsumptions $u^j: \mathcal{D}j \to \varrho$ satisfy $u^j = u^{j'} \circ \mathcal{D}f$ for all $f: j \to j'$. For all $\mathcal{J}$-objects $j$ and $k$ let $c_j^k := u_1^j \circ \varrho i \circ u_2^k: (\mathcal{D}k)I \to (\mathcal{D}j)D$, since

$$ (\mathcal{D}j)d \circ c_j^k = \varrho d \circ \varrho i \circ u_2^k = \varrho(d \circ i) \circ u_2^k = (\mathcal{D}k)(d \circ i), $$

then $c_j^k$ is also a $\mathcal{C}\backslash\mathcal{G}$-morphism from $(\mathcal{D}k)(d \circ i)$ to $(\mathcal{D}j)d = (\text{CTOR} \circ \mathcal{D})j$. We also have

$$ (\text{CTOR} \circ \mathcal{D})f \circ c_{j'}^k = (\mathcal{D}f)_1 \circ u_1^{j'} \circ \varrho i \circ u_2^k = (u^{j'} \circ \mathcal{D}f)_1 \circ \varrho i \circ u_2^k = c_j^k, $$

hence $((\mathcal{D}k)(d \circ i), (c_j^k)_{j \in \mathcal{J}})$ is a natural source for $\text{CTOR} \circ \mathcal{D}$. This is a coherence system for $\mathcal{D}$ since $c_k^k = (\mathcal{D}k)i$ and for all $f: k \to k'$

$$ c_{j'}^{k'} \circ (\mathcal{D}f)_2 = u_1^j \circ \varrho i \circ (u^{k'} \circ (\mathcal{D}f))_2 = c_j^k. $$

□

Hence coherence appears as a necessary condition for $\mathcal{D}$ to have a colimit, but we can be more precise than this.

**Corollary 3.** For every $u: \varrho \to \varrho'$, the coherence system associated to $((u \circ u^j)_{j \in \mathcal{J}}, \varrho')$ is the same as the coherence system associated to $((u^j)_{j \in \mathcal{J}}, \varrho)$.

*Proof.* Trivial since $(u \circ u^j)_1 \circ \varrho' i \circ (u \circ u^k)_2 = u_1^j \circ u_1 \circ \varrho' i \circ u_2 \circ u_2^k = u_1^j \circ \varrho i \circ u_2^k$. □

In order to obtain a correspondence inverse to the one exposed in Lemma 2, we need the following restriction.

**Definition 7.** A coherence system for $\mathcal{D}$ is effective if there exists a natural sink for $\mathcal{D}$ with this coherence system. $\mathcal{D}$ is strictly coherent if it admits a unique effective coherence system.
**Corollary 4.** If $((v^j)_{j \in \mathcal{J}}$, $\varrho$) is a natural sink for $D_c^*$ then $((v^{j \circ (s_j, 1, 1)})_{j \in \mathcal{J}}$, $\varrho$) is a natural sink for D whose associated coherence system is c.

*Proof.* For all $f : j \to j'$, since $v_1^j = v_1^{j'} = 1_D$ then

$$ \begin{aligned} v^{j'} \circ (s_{j'}, 1, 1) \circ D f &= ((D f)_1 \circ s_{j'}, v_2^{j'} \circ (D f)_2, v_3^{j'} \circ (D f)_3) \\ &= ((\mathrm{Ctx} \circ D) f \circ s_{j'}, v_2^{j'} \circ (D_c^* f)_2, v_3^{j'} \circ (D_c^* f)_3) \\ &= (s_j, v_2^j, v_3^j) \\ &= v^j \circ (s_j, 1, 1). \end{aligned} $$

hence $((v^j \circ (s_j, 1, 1))_{j \in \mathcal{J}}$, $\varrho$) is natural for D and its associated coherence system is $s_j \circ \varrho i \circ v_2^k = s_j \circ i_k = c_j^k$ since $v^k : D_c^* k \to \varrho$. $\square$

This entails that if $D_c^*$ has a colimit then c is effective. What may prevent a coherence system from being effective is only a lack of colimits in C. We now investigate the properties of the natural sink for D obtained from a colimit of $D_c^*$.

**Lemma 4.** If $((u^j)_{j \in \mathcal{J}}$, $\varrho$) is a natural sink for D : $\mathcal{J} \to \mathrm{Rpl}(G)$, c is its coherence system and $((v^j)_{j \in \mathcal{J}}$, $\gamma_c$) is a colimit of $D_c^*$ then there exists a unique C-morphism $w : \gamma_c \to \varrho$ such that $w \circ v^k \circ (s_k, 1, 1) = u^k$ for all J-object k.

*Proof.* Since $(\mathrm{Ctx} \circ \varrho, (\mathrm{Ctx} \circ u^j)_{j \in \mathcal{J}})$ is a natural source for $\mathrm{Ctx} \circ D$ there exists a unique $C \backslash G$-morphism $s : \mathrm{Ctx} \circ \varrho \to \overleftarrow{d}$ such that $s_j \circ s = \mathrm{Ctx} \circ u^j = u_1^j$, so that in C we have $s \circ \overleftarrow{d} = \mathrm{Ctx} \circ \varrho = \varrho d$. For every J-objects j and k we have

$$ s_j \circ s \circ \varrho i \circ u_2^k = u_1^j \circ \varrho i \circ u_2^k = c_j^k = s_j \circ (D_c^* k) i $$

by the construction of $D_c^* k$ in Lemma 3, hence $s \circ \varrho i \circ u_2^k = (D_c^* k) i$ since $(s_j)_{j \in \mathcal{J}}$ is a mono-source, and therefore $(s, u_2^k, u_3^k) : D_c^* k \to \varrho$. Besides we have for all $f : k \to k'$

$$ (s, u_2^{k'}, u_3^{k'}) \circ D_c^* f = (s, u_2^{k'} \circ (D_c^* f)_2, u_3^{k'} \circ (D_c^* f)_3) = (s, u_2^k, u_3^k) $$

hence $((s, u_2^k, u_3^k)_{k \in \mathcal{J}}$, $\varrho$) is a natural sink for $D_c^*$ and there exists a unique $w : \gamma_c \to \varrho$ such that $w \circ v^k = (s, u_2^k, u_3^k)$ for all k, so that $w \circ v^k \circ (s_k, 1, 1) = (s_k \circ s, u_2^k, u_3^k) = u^k$. $\square$

This means that this natural sink for D is initial for the natural sinks whose coherence system is c.

**Theorem 3.** D has a colimit iff D is strictly coherent with coherence system c and $\mathrm{Itf} \circ D$, $\mathrm{Ext} \circ D$, $\mathrm{Res} \xrightarrow{d} D_c^*$ have colimits.
*Proof. Sufficient condition.* Since $\mathrm{Itf} \circ \mathbf{D} = \mathrm{Itf} \circ D_c$ and $\mathrm{Ext} \circ \mathbf{D} = \mathrm{Ext} \circ D_c$ (by omitting the obvious inclusion functors) then by Theorem 1 there is a colimit $((v^j)_{j \in \mathcal{J}}, \gamma_c)$ of $D_c$. Any natural sink for $\mathbf{D}$ has coherence system $c$, and since $((v^k \circ (s_k, 1, 1))_{k \in \mathcal{J}}, \gamma_c)$ is a natural sink for $\mathbf{D}$ by Corollary 4, then it is a colimit of $\mathbf{D}$ by Lemma 4.

*Necessary condition.* Obvious by Theorems 2 and 1. □

**Corollary 5.** If $\mathcal{C}$ has pushouts then $\mathbf{D}$ has a colimit iff $\mathbf{D}$ has a unique coherence system and $\mathrm{Itf} \circ \mathbf{D}$, $\mathrm{Ext} \circ \mathbf{D}$ have colimits.

*Proof.* We first notice that if $\mathrm{Itf} \circ \mathbf{D}$ and $\mathrm{Ext} \circ \mathbf{D}$ have colimits then for any coherence system $c$ for $\mathbf{D}$, $D_c$ has a colimit by Corollary 2, hence $c$ is effective by Corollary 4. Then the proof is the same as Theorem 3 only using Corollary 2 instead of Theorem 1. □

We can therefore propose an algorithm for computing a colimit of $\mathbf{D}$, provided the sets of $\mathcal{C}$-morphisms from the interfaces $(\mathbf{D}k)I$ to the contexts $(\mathbf{D}j)D$ are finite for all $\mathcal{J}$-objects $j, k$.

1. Compute the set $\mathcal{C}$ of coherence systems for $\mathbf{D}$. If $\mathcal{C}$ is empty then $\mathbf{D}$ has no colimit by Theorem 2.

2. Compute a limit $(\overleftarrow{d}, (s_j)_{j \in \mathcal{J}})$ of $\mathrm{Ctx} \circ \mathbf{D}$.

3. Compute the set $\Gamma$ of colimits of $D_c$ for all $c \in \mathcal{C}$ using Theorem 1 or Corollary 2, i.e., by computing the relevant colimits in $\mathcal{C}$ if possible.

4. If $\Gamma$ is empty or has more than one element, then $\mathbf{D}$ has no colimit by Theorem 2.

5. If $\mathcal{C}$ has one element $c$ and $\Gamma$ has one element $((v^j)_{j \in \mathcal{J}}, \gamma_c)$ then $((v^j \circ (s_j, 1, 1))_{j \in \mathcal{J}}, \gamma_c)$ is a colimit of $\mathbf{D}$ by Theorem 3.

6. Otherwise $\Gamma$ has one element $((v^j)_{j \in \mathcal{J}}, \gamma_c)$ of coherence system $c$ and $\mathcal{C}$ as at least one element other than $c$, then $((v^k \circ (s_k, 1, 1))_{k \in \mathcal{J}}, \gamma_c)$ is a colimit of $\mathbf{D}$ iff all natural sinks for $\mathbf{D}$ have coherence system $c$.

In Step 4, if $\Gamma$ is empty then we have been unable to find a colimit for $\mathrm{Itf} \circ \mathbf{D}$, $\mathrm{Ext} \circ \mathbf{D}$ or $\mathrm{Res}_{\overleftarrow{d}} \circ D_c$ for any $c \in \mathcal{C}$. Since any effective coherence system must be in $\mathcal{C}$, we conclude by Theorem 2 that $\mathbf{D}$ has no colimit.

If $\Gamma$ has more than one element then we get more than one effective coherence system (by Corollary 4) and the conclusion is the same. From a pratical point of view, we may still use any natural sink for $\mathbf{D}$ computed from the elements of $\Gamma$. It could be selected either by hand or automatically by some criterion to be determined. One possibility is to distinguish in the non-linear contexts, among the copies of items of $\mathcal{G}$, one that is considered as the original, and then consider only the coherence system that uses this original and not its copies.

When only linear replacements are involved there is at most one possible choice.

**Property 1.** If $\mathbf{D} : \mathcal{J} \to \mathrm{Rpl}^*(\mathcal{G})$ is coherent and $\mathrm{Ctx} \circ \mathbf{D}$ has a limit then $\mathbf{D}$ has a unique coherence system.
*Proof.* Let $\overleftarrow{d}, (s_j)_{j \in \mathcal{J}}$) be a limit of $\text{CTOR} \circ \mathcal{D}$ and $b, c$ two coherence systems for $\mathcal{D}$. Since $(\text{CTOR} \circ \mathcal{D})j$ is monic for all $j$ then so are $s_j : \overleftarrow{d} \to (\text{CTOR} \circ \mathcal{D})j$ and the limit $\overleftarrow{d}$. By coherence of $b, c$ there exist unique $\mathcal{C}\backslash\mathcal{G}$-morphisms $i_k : (\mathcal{D}k)(d \circ i) \to \overleftarrow{d}$ and $i'_k : (\mathcal{D}k)(d \circ i) \to \overleftarrow{d}$ such that $s_j \circ i_k = c_j^k$ and $s_j \circ i'_k = b_j^k$, hence $\overleftarrow{d} \circ i_k = (\mathcal{D}k)(d \circ i) = \overleftarrow{d} \circ i'_k$, so that $i_k = i'_k$ and therefore $c_j^k = b_j^k$. □

Hence Step 6 cannot be reached if $\mathcal{D}$ is linear, nor if $\mathcal{C}$ has pushouts since then $\Gamma$ and $\mathcal{C}$ have the same number of elements. Otherwise it may be reached and then we get a natural sink that cannot be guaranteed to be a colimit of $\mathcal{D}$, unless $\mathcal{D}$ has a colimit. If $\mathcal{D}$ has a colimit of coherence system $c$ and Step 6 is reached, then $\mathcal{D}$ has non-effective coherence systems (by Theorem 2) and a colimit of $D_c^*$ has been computed, hence a colimit of $\mathcal{D}$ is indeed obtained (Theorem 3).

An interesting point is that to get an initial object (a colimit of the empty diagram) in $\text{Rpl}(\mathcal{G})$ we need an initial object $\emptyset$ in $\mathcal{C}$, that exists by our hypothesis on $\mathcal{C}$, but no terminal object since $\mathcal{L}_G$ is a terminal object of $\mathcal{C}\backslash\mathcal{G}$. The initial replacement is

<figure><img src="image_20.png" /></figure>

that removes/duplicates nothing and adds/merges nothing. A terminal object in $\mathcal{C}$ is never needed, which is relevant in Example 2 and also in the category of monographs [6].

# 6 Related and Future Work

Parallel graph rewriting originated in [9] that introduced the notion of parallel independence. This problem has been systematically investigated in algebraic approaches to Graph Transformations, see [8] and the more recent contributions [7,15,14], and also in more general frameworks, see [2].

Non independent parallelism has been considered in the Double-Pushout approach [17] where rules can be amalgamated by agreeing on common deletions and creations. In [13], a framework based on the algebraic Single-Pushout approach has been proposed where conflicts between parallel transformations are allowed but requires the user to solve them by providing the right control flow.

The present work stems from [3] where an algorithmic framework is proposed for rule-based deterministic parallel transformations of graphs with sets of attributes. Replacements and effective coherence systems evolved from the algebraic approach in [4] extended in [5]. The idea of considering general colimits comes from the reconstruction step of Global Transformations [16].

The connection between rule-based transformations and replacements, and how to specify diagrams of replacements from rule systems, has been sketched in [5] and will be developed in a forthcoming paper.
References

1. Adámek, J., Herrlich, H., Strecker, G.E.: Abstract and Concrete Categories - The Joy of Cats. Online Edition (2004), http://katmat.math.uni-bremen.de/acc/

2. Behr, N., Harmer, R., Krivine, J.: Fundamentals of compositional rewriting theory. J. Log. Algebraic Methods Program. **135**, 100893 (2023). https://doi.org/10.1016/J.JLAMP.2023.100893

3. Boy de la Tour, T., Echahed, R.: Parallel rewriting of attributed graphs. Theoretical Computer Science **848**, 106–132 (2020). https://doi.org/10.1016/j.tcs.2020.09.025

4. Boy de la Tour, T., Echahed, R.: Parallel coherent graph transformations. In: Recent Trends in Algebraic Development Techniques, 25th International Workshop, WADT 2020, Revised Selected Papers. LNCS, vol. 12669, pp. 75–97. Springer (2021). https://doi.org/10.1007/978-3-030-73785-6_5

5. Boy de la Tour, T.: Subsumptions of algebraic rewrite rules. In: Staton, S., Vasilakopoulou, C. (eds.) Proceedings of the Sixth International Conference on Applied Category Theory 2023. EPTCS, vol. 397, pp. 20–38. Open Publishing Association (2023). https://doi.org/10.4204/EPTCS.397.2

6. Boy de la Tour, T.: Algebraic properties and transformations of monographs. Theoretical Computer Science **1024**, 114939 (2025). https://doi.org/https://doi.org/10.1016/j.tcs.2024.114939, https://www.sciencedirect.com/science/article/pii/S0304397524005565

7. Corradini, A., Duval, D., Löwe, M., Ribeiro, L., Machado, R., Costa, A., Azzi, G., Bezerra, J.S., Rodrigues, L.M.: On the essence of parallel independence for the double-pushout and sesqui-pushout approaches. In: Heckel, R., Taentzer, G. (eds.) Graph Transformation, Specifications, and Nets - In Memory of Hartmut Ehrig. LNCS, vol. 10800, pp. 1–18. Springer (2018). https://doi.org/10.1007/978-3-319-75396-6_1

8. Ehrig, H., Kreowski, H.J., Montanari, U., Rozenberg, G. (eds.): Handbook of Graph Grammars and Computing by Graph Transformation, Volume 3: Concurrency, Parallelism and Distribution. World Scientific (1999)

9. Ehrig, H., Kreowski, H.: Parallelism of manipulations in multidimensional information structures. In: Mathematical Foundations of Computer Science. LNCS, vol. 45, pp. 284–293. Springer (1976). https://doi.org/10.1007/3-540-07854-1_188

10. Fernandez, A., Maignan, L., Spicher, A.: Cellular automata and kan extensions. In: Castillo-Ramirez, A., Guillon, P., Perrot, K. (eds.) 27th IFIP WG 1.5 International Workshop on Cellular Automata and Discrete Complex Systems, AUTOMATA 2021. OASICS, vol. 90, pp. 7:1–7:12. Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2021). https://doi.org/10.4230/OASICS.AUTOMATA.2021.7

11. Gardner, M.: Mathematical games – the fantastic combinations of John Conway’s new solitaire game "life". Scientific American **223**, 120–123 (Oct 1970)

12. Herrlich, H., Strecker, G.E.: Category Theory. Allyn and Bacon (1973)

13. Kniemeyer, O., Barczik, G., Hemmerling, R., Kurth, W.: Relational growth grammars - A parallel graph transformation approach with applications in biology and architecture. In: Third International Symposium AGTIVE, Revised Selected and Invited Papers. pp. 152–167 (2007). https://doi.org/10.1007/978-3-540-89020-1_12

14. Kreowski, H., Kuske, S., Lye, A.: A simple notion of parallel graph transformation and its perspectives. In: Graph Transformation, Specifications, and Nets - In Memory of Hartmut Ehrig. LNCS, vol. 10800, pp. 61–82. Springer (2018)
15. Löwe, M.: Characterisation of parallel independence in AGREE-rewriting. In: 11th ICGT. LNCS, vol. 10887, pp. 118–133. Springer (2018)

16. Maignan, L., Spicher, A.: Global graph transformations. In: Plump, D. (ed.) Proceedings of the 6th International Workshop on Graph Computation Models. CEUR Workshop Proceedings, vol. 1403, pp. 34–49. CEUR-WS.org (2015), http://ceur-ws.org/Vol-1403/paper4.pdf

17. Taentzer, G.: Parallel high-level replacement systems. Theoretical Computer Science 186, 43–81 (1997)