Parallel Independence in Attributed Graph Rewriting
Thierry Boy de la Tour
Univ. Grenoble Alpes, CNRS, Grenoble INP, LIG, 38000 Grenoble, France
thierry.boy-de-la-tour@imag.fr

We use graphs where vertices and arrows are attributed with sets of values, and rules that allow todelete data from a graph, to create new vertices or arrows, and to include values in attributes. Rules
may be applied simultaneously, yielding a notion of parallelism that generalizes cellular automata inparticular by allowing infinite matchings of rules in a graph. This is first used to define a notion ofsequential independence of a set M of matchings of rules, even when M is infinite. Next, a notion ofparallel independence of matchings is defined that accounts for the particular treatment of attributes,
and it is proven to characterize sequential independence. Last, the effective deletion property, acondition that ensures that rules can be applied in parallel without conflicts, is proven to generalize
parallel independence.

1

Introduction

The notion of parallel independence has been studied mostly in the algebraic approach to graph rewriting,see [1] and the references therein. It basically consists in a condition on concurrent transformations ofan object that characterizes the possibility to apply the transformations sequentially in any order suchthat all such sequences of transformations yield the same result. When two transformations are involved
this takes the form of the diamond property and is known as the Local Church-Rosser Problem. Parallel
independence then allows to define critical pairs, a central notion in Term and Graph Rewriting.
This problem should therefore also be considered in algorithmic approaches to graph rewriting. Indeed, the informal description of parallel independence given above makes perfect sense out of the algebraic approach; it is purely operational. Consider for instance Python’s multiple assignment a, b := b, athat swaps the values of a and b. We naturally understand this as a parallel expression a := b k b := a. If
a and b have the same value then the two assignments can be evaluated in sequence in any order; they areparallel independent. If however they have distinct values, the two sequential evaluations yield different
results (and none corresponds to the intended meaning); the two assignments are parallel dependent.
Parallel dependence typically occurs in cellular automata when the local rule is applied to neighbor cells(because of the overlap); thus sequential applications of the local rule would result in non deterministic
automata. It is therefore necessary to define a parallel transformation that handles parallel dependence.
One has been described in [6], where graphs are attributed by sets of values (see Sections 2 and 3). Sets
are convenient because they allow to add as many values as required, just as new vertices and arrows canalways be added (see Section 6 for a more precise argument).
But there is a fundamental difference between the two, that lies in the semantics of the rules describedin Section 3: vertices and arrows are always added as new objects, but values are added by inclusion in
attributes, where they may not be new. This is different from E-graphs, an alternate notion of attributedgraphs with any number of values (see [3]), and is bound to have an impact on parallel independence.
We are first faced with the same difficulty as in the algebraic approach, that is to apply transformations meant for the same graph in sequence, hence on already transformed graphs (except for the one
considered first). This is solved in Section 4 by taking advantage of the parallel transformation defined
Submitted to:
TERMGRAPH 2020c T. Boy de la TourThis work is licensed under theCreative Commons Attribution License.

2

Parallel Independence in Attributed Graph Rewritingin Section 3. In Section 5 a definition of parallel independence adapted to the present framework is given,and proven to be correct since it is equivalent to sequential independence. Finally, Section 6 is devoted tothe effective deletion property from [6], a condition that guarantees that parallel rules do not clash. It is
proved that parallel independence entails effective deletion, hence that the latter tolerates more overlaps
than the former. The proofs can be found in [4].

2Attributed Graphs

We assume a many-sorted signature Σ and a set V of variables, disjoint from Σ, such that every variable
has a Σ-sort. For any finite X ⊆ V , T (Σ , X) denotes the algebra of Σ-terms over X.
~ Ǵ, G̀, AG , G̊) where Ġ, G~ are sets, Ǵ, G̀
An attributed graph (or graph for short) G is a tuple (Ġ, G,~ to Ġ, AG is a Σ-algebra and G̊ is an attribution of G, i.e., a
are the source and target functions from G~
function from Ġ ∪ G to P(bAG c) (the carrier set bAG c of AG is the disjoint union of the carrier sets of~ and bAG c are pairwise disjoint; their elements are respectively
the sorts in AG ). We assume that Ġ, G~ it is finite if the setscalled vertices, arrows and attributes. G is unlabelled if G̊(x) = ∅ for all x ∈ Ġ ∪ G,
def
~ and G̊(x) are finite. The carrier of G is the set bGc = Ġ ∪ G~ ∪ bAG c.
Ġ, G~ H́, H̀) of H is a subgraph
A graph H is a subgraph of G, written H C G, if the underlying graph (Ḣ, H,~
of G’s underlying graph (in the usual sense), AH = AG and H̊(x) ⊆ G̊(x) for all x ∈ Ḣ ∪ H.
A morphism α from graph H to graph G is a function from bHc to bGc such that the restriction of α
~ is a morphism from H’s to G’s underlying graphs (that is, Ǵ ◦ α = α ◦ H́ and G̀ ◦ α = α ◦ H̀,
to Ḣ ∪ H
this restriction of α is called the underlying graph morphism of α), the restriction of α to bAH c is a
~ Note thatΣ-homomorphism from AH to AG , denoted α̊, and α̊ ◦ H̊(x) ⊆ G̊ ◦ α(x) for all x ∈ Ḣ ∪ H.
H C G iff bHc ⊆ bGc and the canonical injection from bHc to bGc is a morphism from H to G. A
morphism α is a matching if the underlying graph morphism of α is injective. α is an isomorphism if α
and α −1 are bijective morphisms, hence iff the underlying graph morphism of α is an isomorphism, α̊ isa Σ-isomorphism and α̊ ◦ H̊ = G̊ ◦ α. For all F C H, the image α(F) is the smallest subgraph of G w.r.t.
the order C such that α|bFc is a morphism from F to α(F).
Given two attributions l and l 0 of G let l \ l 0 (resp. l ∩ l 0 , l ∪ l 0 ) be the attribution of G that maps any
x to l(x) \ l 0 (x) (resp. l(x) ∩ l 0 (x), l(x) ∪ l 0 (x)). If l is an attribution of a subgraph H C G, it is implicitly~ and maps any other entry to ∅.
extended to the attribution of G that is identical to l on Ḣ ∪ H
Unions of graphs can only be formed between joinable graphs, i.e., graphs that have a common part.
We start with a simpler notion of joinable functions.
Definition 2.1 (joinable functions). Two functions f : D → C and g : D0 → C0 are joinable if f (x) = g(x)for all x ∈ D ∩ D0 . Then, the meet of f and g is the function f f g : D ∩ D0 → C ∩C0 that is the restrictionof f (or g) to D ∩ D0 . The join f g g is the unique function from D ∪ D0 to C ∪C0 such that f = ( f g g)|Dand g = ( f g g)|D0 .
For any set I and any I-indexed family ( fi : Di → Ci )i∈I of pairwise
joinable functions, let gi∈I fi beSS
the only function from i∈I Di to i∈I Ci such that fi = gi∈I fi |Di for all i ∈ I.
We see that any two restrictions f |A and f |B of the same function f are joinable, and then f |A f f |B =f |A∩B and f |A g f |B = f |A∪B . Conversely, if f and g are joinable then each is a restriction of f g g.
~ =H
~ ∩ Ġ = ∅,Definition 2.2 (joinable graphs). Two graphs H and G are joinable if AH = AG , Ḣ ∩ G
and the functions H́ and Ǵ (and similarly H̀ and G̀) are joinable. We can then define the graphsdef~ H́ f Ǵ, H̀ f G̀, AH , H̊ ∩ G̊ ),~ ∩ G,
H u G = ( Ḣ ∩ Ġ, H
def~ H́ g Ǵ, H̀ g G̀, AH , H̊ ∪ G̊ ).
~ ∪ G,
H t G = ( Ḣ ∪ Ġ, H

T. Boy de la Tour

3

Similarly, if (Gi )i∈I is an I-indexed family of graphs that are pairwise joinable, and A is an algebra such
[
[
[
G
def
~ i , gi∈I Ǵi , gi∈I G̀i , A , G̊i ).
that A = AGi for all i ∈ I, then let Gi = ( Ġi , G
i∈I

i∈I

i∈I

i∈I

It is easy to see that these structures are graphs: the sets of vertices and arrows are disjoint and theadjacency functions have the correct domains and codomains. If I = ∅ the chosen algebra A is generally
obvious from the context. We see that any two subgraphs of G are joinable, and that H C G iff H u G = H
iff H t G = G. These operations are commutative and, on triples of pairwise joinable graphs, they areassociative and distributive over each other.
~ ∩ A = ∅ and
For any sets V , A and attribution l, we say that G is disjoint from V, A, l if Ġ ∩V = ∅, G
~ We write G \ [V, A, l] for the largest subgraph of G (w.r.t. C) that isG̊(x) ∩ l(x) = ∅ for all x ∈ Ġ ∪ G.
disjoint from V, A, l. This provides a natural way of removing objects from an attributed graph. It is easy
to see that this subgraph always exists (it is the union of all subgraphs of G disjoint from V, A, l), hence
rewriting steps will not be restricted by a gluing condition as in the Double-Pushout approach (see [3]).

3Applying Rules in Parallel

Definition 3.1 (rules, matchings). For any finite X ⊆ V , a (Σ, X)-graph is a finite graph G such that

S
def S
AG = T (Σ , X). Let Var(G) = x∈Ġ∪G~
t∈G̊(x) Var(t) , where Var(t) is the set of variables occurring
in t.
A rule r is a triple (L, K, R) of (Σ, X)-graphs such that L and R are joinable, L u R C K C L andVar(L) = X (see Remark 3.2 below).
A matching µ of r in a graph G is a matching from L to G such that µ̊(L̊(x) \ K̊(x)) ∩ µ̊(K̊(x)) = ∅~ We denote M (r, G) the set of(or equivalently µ̊(L̊(x) \ K̊(x)) = µ̊(L̊(x)) \ µ̊(K̊(x))) for all x ∈ K̇ ∪ K.
all matchings of r in G (they all have domain bLc).
We consider finite sets R of rules such that for all r, r0 ∈ R, if (L, K, R) = r 6= r0 = (L0 , K 0 , R0 ) thenUbLc 6= bL0 c, so that M (r, G)∩M (r0 , G) = ∅ for any graph G; we then write M (R, G) for r∈R M (r, G).
For any µ ∈ M (R, G) there is a unique rule rµ ∈ R such that µ ∈ M (rµ , G), and its components aredenoted rµ = (Lµ , Kµ , Rµ ).
Remark 3.2. If X were allowed to contain a variable v not occurring in L, then v would freely match any
element of AG and the set M (r, G) would contain as many matchings with essentially the same effect.
Also note that Var(R) ⊆ Var(L), R and K are joinable and R u K = L u R. The fact that K is not required
to be a subgraph of R allows the possible deletion by other rules of data matched by K but not by R. Thisfeature enables a straightforward representation of cellular automata (see [5]).
A rewrite step may involve the creation of new vertices in a graph, corresponding to the vertices of arule that have no match in the input graph, i.e., those in Ṙ \ L̇ (or similarly may create new arrows). Thesevertices should really be new, not only different from the vertices of the original graph but also different
from the vertices created by other transformations (corresponding to other matchings in the graph). Thisis computationally easy to do but not that easy to formalize in an abstract way. We simply reuse thevertices x from Ṙ \ L̇ by indexing them with any relevant matching µ, each time yielding a new vertex(x, µ) which is obviously different from any new vertex (x, ν) for any other matching ν 6= µ, and also
from any vertex of G.
Definition 3.3 (graph G↑µ and matching µ↑). For any rule r = (L, K, R), graph G and µ ∈ M (r, G) we
define a graph G↑µ together with a matching µ↑ of R in G↑µ . We first define the sets
~ ↑µ = µ(~R ∩ K)~ ] ((~R \ K)
~ × {µ}).
Ġ↑µ = µ(Ṙ ∩ K̇) ] ((Ṙ \ K̇) × {µ}) and G
def

def

4

Parallel Independence in Attributed Graph Rewriting

def
def
def
~ then µ↑(x) =Next we define µ↑ by: µ̊↑ = µ̊ and for all x ∈ Ṙ ∪ ~R, if x ∈ K̇ ∪ Kµ(x) else µ↑(x) = (x, µ).
Since the restriction of µ↑ to Ṙ ∪ ~R is bijective, then µ↑ is a matching from R to the graphdef~ ↑µ , µ↑ ◦ Ŕ ◦ µ↑−1 , µ↑ ◦ R̀ ◦ µ↑−1 , AG , µ̊↑ ◦ R̊ ◦ µ↑−1 ).
G↑µ = ( Ġ↑µ , G

By construction µ↑(R) = G↑µ , µ and µ↑ are joinable and µ f µ↑ is a matching from RuK to µ(RuK).
It is easy to see that the graph G and the graphs G↑µ are pairwise joinable.
For any set M ⊆ M (R, G) of matchings in a graph G we define below how to transform G by
applying simultaneously the rules associated with matches in M.
Definition 3.4 (graph GkM ). For any graph G, set M ⊆ M (R, G) and matching µ ∈ M (R, G), let
defG

GkM = G \ [VM , AM , `M ] t

G↑µ where

µ∈M
def

VM =

[

def

µ(L̇µ \ K̇µ ), AM =defµ(~Lµ \ ~Kµ ) and `M =

[
µ∈M

µ∈M

[

µ̊ ◦ (L̊µ \ K̊µ ) ◦ µ −1 .

µ∈M

If M is a singleton {µ} we write Gkµ for GkM , Vµ for VM , etc.
GkM is guaranteed to be a graph since the t operation is only applied on joinable graphs. Everymorphism µ↑ is a matching from the right hand side Rµ to the result GkM of the transformation. The
case where M is a singleton defines the classical semantics of one sequential rewrite step.
Definition 3.5 (sequential rewriting). For any finite set of rules R, we define the relation →R of sequential rewriting by stating that, for all graphs G and H,
G →R H iff there exists some µ ∈ M (R, G) such that H ' Gkµ .

4

Sequential Independence

In the Double-Pushout approach to graph rewriting (see [3]), sequential independence is a property of
two consecutive direct transformations, formulated as the existence of two commuting morphisms j1 andj2 as shown below.
L1

K1

R1

L2

j2

µ1

K2

R2

D2

H2

j1
µ2

G

D1

H1

It is then proven by the Local Church-Rosser Theorem that the two production rules can be applied inreverse order to G and yield the same result H2 (we may call this the swapping property). Of course, thematchings µ1 and µ2 are then replaced by other matchings that are related to µ1 and µ2 . A drawbackof this definition is that it does not account for longer sequences of direct transformations. Indeed, if
three consecutive steps are given by (µ1 , µ2 , µ3 ), it is possible to swap µ1 with µ2 if they are sequential
independent, and similarly for µ2 and µ3 , but this does not imply that µ1 and µ3 can be swapped underthese hypotheses (because the matchings, and hence the direct transformations, are modified by theswapping operations). We would need to express sequential independence between µ1 and µ3 , but theT. Boy de la Tour5

definition does not apply since they are not consecutive steps. More elaborate notions of equivalence
between sequences of direct transformations are thus required (see [2]).
Because of the specificities of our framework (no pushouts, horizontal morphisms are only canonicalinjections, and we do not have such a morphism from K to R) we need a different definition of sequential
independence. It is natural to think of the swapping property as the definition, since it describes theoperational meaning of parallel independence, but we are faced with another problem. We are dealing
with possibly infinite sets of matchings of rules in a graph, and we cannot form a notion of infinite
sequences of rewrite steps (because each step may both remove and add data). Yet we do not wish to
restrict the notion to finite sets, not simply for the sake of generality but also because it is closely related
to parallel independence, a notion that can naturally be defined on infinite sets (see below).
We may however use Definition 3.4 to handle infinite sets of matchings, and thus express sequential
independence as the possibility to apply any rule after the others (and these can be applied in parallel),yielding the same result as a parallel transformation with the whole set of matchings. Yet this definition
would not imply that subsets of a sequential independent set are sequential independent, hence it needs
to be stated for all subsets.
Definition 4.1. For any graph G and set M ⊆ M (R, G), we say that M is sequential independent if for
all M 0 ⊆ M and all µ ∈ M \ M 0 ,• µ(Lµ ) C GkM0 , hence there is a is canonical injection j from µ(Lµ ) to GkM0 ,• there exists an isomorphism α such that α(GkM0 ∪{µ} ) = GkM0 k j◦µ and α is the identity on G.
The isomorphism α in Definition 4.1 is necessary to account for the difference between the isomorphic graphs µ↑(Rµ ) and ( j ◦ µ)↑(Rµ ).
It is then easy to see (by induction on the cardinality of M) that
Proposition 4.2. For any graph G and finite set M ⊆ M (R, G), if M is sequential independent then
G →?R GkM .
Of cours there is usually more than one sequence of rewriting steps from G to GkM , since under the
hypothesis they can be swapped; but without it there is generally none (as illustrated in Section 1). And
the fact that there is one such sequence does not imply sequential independence, i.e., the converse of
Proposition 4.2 is obviously not true.

5

Parallel Independence

In the Double-Pushout approach, parallel independence is a property of two direct transformations of thesame object G, formulated as the existence of two commuting morphisms j1 and j2 as shown below.
R1

K1

L1

L2

j2

K2

R2

D2

H2

j1
µ1 µ2

H1

D1

G

This definition can easily be lifted to sets of matchings (or direct transformations) by considering
all possible pairs of matchings, with a slight caveat. In this definition the two direct transformations
may be identical, thus stating a property of a single transformation that is clearly not shared by all. But

6Parallel Independence in Attributed Graph Rewriting

Definition 3.4 does not allow to apply any member µ of M more than once (because applying µ any
number of times in parallel would jeopardize determinism). For this reason any singleton M shall beconsidered as parallel independent.
The Local Church-Rosser Theorem mentioned above actually shows that µ1 and µ2 are parallel
independent iff they correspond to a sequential independent pair (µ1 , µ20 ), where µ2 and µ20 are related. It
is the symmetry between µ1 and µ2 that entails the swapping property. This is remarquable since parallel
independence does not refer to the results of the direct transformations involved.
Our goal is therefore to formulate parallel independence in the present framework, in order to obtain
an equivalence similar to the Local Church-Rosser Theorem. Considering that the pushout complement
D1 is replaced by the graph G \ [Vµ1 , Aµ1 , `µ1 ], the commuting property of j2 amounts to µ2 (L2 ) C G \[Vµ1 , Aµ1 , `µ1 ], that can be more elegantly expressed as µ2 (L2 ) u µ1 (L1 ) C µ1 (K1 ). This simply meansthat any graph item that is matched twice cannot be removed.
However, our treatment of attributes makes it possible to recover in the right hand side an attributethat has been deleted in the left hand side (this is of course not possible for vertices or arrows). Thispossibility should therefore be accounted for in the notion of parallel independence, i.e., an attribute thatis matched twice may be deleted provided it is recovered. We also need to consider what it means for an
attribute to be matched: it may be the case that an (occurrence of an) attribute is matched by ν↑ but notby ν (i.e., it corresponds to an occurrence of a term in the right hand side of a rule but to none in the left
hand side). This leads to the following definition.
Definition 5.1. For any graph G and set M ⊆ M (R, G), we say that M is parallel independent ifµ(Lµ ) u (ν(Lν ) t ν↑(Rν )) C µ(Kµ ) t µ↑(Rµ ) for all µ, ν ∈ M such that µ 6= ν.
This definition may seem strange, but it is easy to see that on unlabelled graphs it amounts to ν(Lν ) uµ(Lµ ) C µ(Kµ ) for all µ 6= ν, i.e., to the standard algebraic notion of parallel independence (translated
to the present framework). But the best justification for the definition is the following result.
Theorem 5.2. For any graph G and set M ⊆ M (R, G), M is parallel independent iff M is sequential
independent.
Thus Definition 5.1 arises as a characterization of sequential independence that does not refer to theresults of the transformations, and indeed that does not rely on Definition 3.4, though of course it does
rely on Definitions 2.2, 3.1 and 3.3. Note also that Definition 5.1 depends explicitly on right hand sides
of rules, in contrast with the general algebraic definition of parallel independence given above, or with
the Essential Condition of parallel independence in [1].

6The Effective Deletion Property

We have not yet defined a relation of parallel rewriting as we did for sequential rewriting (Definition 3.5).
The reason is that two matchings may conflict as one retains (in R u K) what another removes. The transformation offered by Definition 3.4 performs deletions before unions, which means that these conflicts
are resolved by giving priority to retainers over removers. But if the deletion actions of a rule are notexecuted in a parallel transformation, how can we claim that this rule has been executed (or applied) inparallel with others? Thus, in order to define parallel rewriting with a clear semantics we need to ruleout such conflicts.
One possibility is to translate to the present framework the notion of parallel coherence that has beendevised in order to define algebraic parallel graph transformation (see [5]). This is is a property of two

T. Boy de la Tour7

direct transformations of the same object G, formulated as the existence of two commuting morphisms
j1 and j2 as shown below.
R1

I1

K1

L1
j1

H1

L2

µ1

D1

µ2

K2

I2

R2

j2

G

D2

H2

This notion clearly generalizes algebraic parallel independence. In the present framework the object
I2 is replaced by the graph K2 u R2 , hence the commuting property of j2 amounts to µ2 (K2 u R2 ) C
G \ [Vµ1 , Aµ1 , `µ1 ], that can be expressed as µ2 (K2 u R2 ) u µ1 (L1 ) C µ1 (K1 ). This simply means that any
graph item that is matched by some K u R cannot be removed by any rule.
Definition 6.1. For any graph G and set M ⊆ M (R, G), we say that M is parallel coherent ifµ(Lµ ) u ν(Kν u Rν ) C µ(Kµ ) for all µ, ν ∈ M.
The problem here as above is that deleted attributes can be recovered by the right hand side of rules,
and that this possibility is not accounted for in the algebraic definitions, since these do not distinguishbetween graph items and attributes. This leads to the following definition (see [6]).
Definition 6.2 (effective deletion property, full parallel rewriting). For any graph G, a set M ⊆ M (R, G)↑
is said to satisfy the effective deletion property if GkM is disjoint from VM , AM , `M \ `M
, where
↑
`M
=
def

[

µ̊ ◦ (R̊µ \ K̊µ ) ◦ µ −1 .

µ∈MFor any finite set of rules R, we define the relation ⇒R of full parallel rewriting by stating that, forall graphs G and H,
G ⇒R H iff M (R, G) has the effective deletion property and H ' GkM (R,G) .
It can be shown that ⇒R is deterministic up to isomorphism, that is, if G ⇒R H, G0 ⇒R H 0 and
G ' G0 then H ' H 0 . In particular, it is possible to represent any cellular automaton by a suitable rule r
and a class of graphs that correspond to configurations of the automaton (every vertex corresponds to acell), such that ⇒r (restricted to such graphs) is the transition function of the automaton.
This representation of cellular automata satisfies the effective deletion property, but it also satisfies
parallel coherence. Hence Definition 6.2 may appear as a weird choice. One motivation behind thepresent work is to support this definition.
Our first argument in favor of Definition 6.2 is that parallel coherence is not sufficient because it does
not generalize parallel independence, as shown by the following example.
Example 6.3. Let us consider rules r1 = (L1 , K1 , R1 ) and r2 = (L2 , K2 , R2 ) where the graphs L1 , K1 andR1 have only one vertex x, the graphs L2 , K2 and R2 have only one vertex y, and the attributes are as
pictured below (u, v are variables and f is a unary function symbol). Let AG be the algebra with carrier
set {1} where f is interpreted as the constant function 1, and let G be the graph that has a unique vertex
a with attribute {1}.

8Parallel Independence in Attributed Graph Rewritingu{u} = L̊1 (x) = K̊1 (x)µ˚1f (u) R̊1 (x) = {u, f (u)}µ˚1G̊(a) = {1}1µ˚2{v} = L̊2 (y)

v

µ˚2

f (v)

R̊2 (y) = { f (v)}K̊2 (y) = ∅There are exactly two matchings of {r1 , r2 } in G: µ1 and µ2 defined by µ1 (x) = a, µ̊1 (u) = 1, µ2 (y) =a and µ̊2 (v) = 1. Let M = {µ1 , µ2 }, we see that M is not parallel coherent since µ1 (R1 uK1 )u µ2 (L2 ) = G
is not a subgraph of µ2 (K2 ). However, we see that M is sequential independent since the matchings canbe applied sequentially in any order, yielding the same graph G.
Our second argument is that the effective deletion property is sufficient because it does generalizeboth parallel coherence and parallel independence.
Theorem 6.4. For any graph G and set M ⊆ M (R, G) if M is parallel independent or parallel coherent
then M has the effective deletion property.
Hence effective deletion encompasses both a general algebraic notion translated to the present (nonalgebraic) framework, and a notion specific to this framework but that relies on an objective fact, that is
Theorem 5.2. This does not mean that no other property is possible (especially a less general one) andthat Definition 6.2 cannot be questioned. It is still a matter of choice, but there is evidence that this is areasonable one. Another important feature is that if M does not have the effective deletion property, we
see that there must be a conflict involving an element of VM , AM or `M . Hence the right hand sides ofrules never create conflicts; this is due to the choice of attributes as sets of values.
We also see that
Corollary 6.5. If M (R, G) is finite and parallel independent then G →?R GkM and G ⇒R GkM .
Hence in this case ⇒R deterministically picks one graph reachable from G by sequential rewriting.

References[1] Andrea Corradini, Dominique Duval, Michael Löwe, Leila Ribeiro, Rodrigo Machado, Andrei Costa, Guilherme Grochau Azzi, Jonas Santos Bezerra & Leonardo Marques Rodrigues (2018): On the Essence of Parallel Independence for the Double-Pushout and Sesqui-Pushout Approaches. In Reiko Heckel & Gabriele
Taentzer, editors: Graph Transformation, Specifications, and Nets - In Memory of Hartmut Ehrig, LNCS
10800, Springer, pp. 1–18.
[2] Andrea Corradini, Ugo Montanari, Francesca Rossi, Hartmut Ehrig, Reiko Heckel & Michael Löwe (1997):
Algebraic Approaches to Graph Transformation - Part I: Basic Concepts and Double Pushout Approach.
In Grzegorz Rozenberg, editor: Handbook of Graph Grammars and Computing by Graph Transformations,
Volume 1: Foundations, World Scientific, pp. 163–246.
[3] Hartmut Ehrig, Karsten Ehrig, Ulrike Prange & Gabriele Taentzer (2006): Fundamentals of Algebraic Graph
Transformation. Monographs in Theoretical Computer Science. An EATCS Series, Springer.
[4] Thierry Boy de la Tour (2020): On Parallel and Sequential Independence in Attributed Graph Rewriting.
Available at http://hal.univ-grenoble-alpes.fr/hal-02549835.
[5] Thierry Boy de la Tour & Rachid Echahed (2019): True Parallel Graph Transformations: an Algebraic Approach Based on Weak Spans. CoRR (abs/1904.08850).
[6] Thierry Boy de la Tour & Rachid Echahed (2020): Combining Parallel Graph Rewriting and Quotient Graphs.
In: 13th International Workshop on Rewriting Logic and its Applications, LNCS, Springer, to appear.