=Paper=
{{Paper
|id=Vol-1403/paper6
|storemode=property
|title=Attribution of Graphs by Composition of M,N-adhesive Categories
|pdfUrl=https://ceur-ws.org/Vol-1403/paper6.pdf
|volume=Vol-1403
|dblpUrl=https://dblp.org/rec/conf/gg/PeuserH15
}}
==Attribution of Graphs by Composition of M,N-adhesive Categories==
https://ceur-ws.org/Vol-1403/paper6.pdf
Attribution of Graphs by Composition
of M, N -adhesive Categories
Christoph Peuser? and Annegret Habel
Carl von Ossietzky Universität Oldenburg
{peuser,habel}@informatik.uni-oldenburg.de
Abstract. This paper continues the work on M, N -adhesive categories
and shows some important constructions on these categories. We use
these constructions for an alternative, short proof for the M, N -adhesive-
ness of partially labelled graphs. We further present a new concept of
attributed graphs and show that the corresponding category is M, N -
adhesive. As a consequence, we inherit all nice properties for M, N -
adhesive systems such as the Local Church-Rosser Theorem, the Paral-
lelism Theorem, and the Concurrency Theorem for this type of attributed
graphs.
Keywords: Graph transformation, attributed graphs, composition, adhesive cat-
egories, adhesive systems
1 Introduction
The double-pushout approach to graph transformation, which was invented in
the early 1970’s, is the best studied framework for graph transformation [Roz97],
[EEKR99, EKMR99, EEPT06b]. As applications of graph transformation come
with a large variety of graphs and graph-like structures, the double-pushout ap-
proach has been generalized to the abstract settings of high-level replacement
systems [EHKP91], adhesive categories [LS05], M-adhesive categories [EGH10],
M, N -adhesive categories [HP12], and W-adhesive categories [Gol12]. This pa-
per continues the work of Habel and Plump [HP12] on M, N -adhesive categories.
In the literature, there are several variants of attribution concepts, e.g. typed
attributed graphs in the sense of Ehrig et al. [EEPT06b], attributed graphs in the
sense of Plump [Plu09], attributed graphs as a graph with a marked sub-graph in
the sense of Kastenberg and Rensink [KR12], separation of the graph structure
and their attribution and data in the sense of Golas [Gol12], and attributed
structures in the sense of Duval et al. [DEPR14].
Our main aim is to introduce a simple, alternative concept for attributed graphs
and attributed graph transformation. Our approach is to define a category
?
This work is supported by the German Research Foundation through the Research
Training Group (DFG GRK 1765) SCARE (www.scare.uni-oldenburg.de).
AttGraphs of attributed graphs from the well-known category Graphs of unla-
belled graphs and a category Att of attribute collections by a multiset construc-
tion and the comma category construction. By closure results for M, N -adhesive
categories, we obtain that the category AttGraphs is M, N -adhesive. By the
results in [HP12], the Local Church-Rosser Theorem, the Parallelism Theorem
and the Concurrency Theorem hold for the new type of attributed graphs pro-
vided that the HLR+ -properties are satisfied.
The paper is structured as follows. In Section 2, we recall the definition of M, N -
adhesive categories. In Section 3, we prove some basic composition results and
show that constructions for a string and a multiset category are M, N -adhesive
for suitable classes M and N provided that the underlying category is. As a con-
sequence, the category of partially labelled graphs is M, N -adhesive, as shown
in Section 4. In Section 5, we introduce a new concept of attributed graphs -
similar to partially labelled graphs - and show that the corresponding category
of attributed graphs is M, N -adhesive. In Section 6, we present a precise rela-
tionship between M, N -adhesive and W-adhesive categories, in Section 7 some
related work, and in Section 8 some concluding remarks.
Note that this paper comes with a long version [PH15] containing the proofs and
additional examples.
2 M, N -adhesive Categories
In this section, we recall the definition of M, N -adhesive categories, introduced
in [HP12], generalizing the one of M-adhesive categories [EGH10]. We assume
that the reader is familiar with the basic concepts of category theory; standard
references are [EEPT06b, Awo10].
Definition 1 (M, N -adhesive). A category C is M, N -adhesive, where M is
a class of monomorphisms and N a class of morphisms, if the following properties
are satisfied:
1. M and N contain all isomorphisms and are closed under composition and
decomposition. Moreover, N is closed under M-decomposition, that is, f ; g ∈
N , g ∈ M implies f ∈ N .
2. C has M, N -pushouts and M-pullbacks. Also, M and N are stable under
pushouts and pullbacks.
3. M, N -pushouts are M, N -van Kampen squares.
Remark. C has M, N -pushouts, if there is a pushout whenever one of the given
morphisms is in M and the other morphism is in N . C has M-pullbacks, if there
exists a pullback whenever at least one of the given morphisms is in M. A class
X ∈ {M, N } is stable under M, N -pushouts if, given the M, N -pushout (1) in
the diagram below, m ∈ X implies n ∈ X and stable under M-pullbacks if, given
the M-pullback (1) in the diagram below, n ∈ X implies m ∈ X . An M, N -
pushout is an M, N -van Kampen square if for the commutative cube (2) in the
diagram below with the pushout (1) as bottom square, b, c, d, m ∈ M, f ∈ N ,
and the back faces being pullbacks, we have that the top square is a pushout if
and only if the front faces are pullbacks.
A0
C0
m
A B B0
c 0
D
f (1) g f A b
m
C d
n
C D n B
(2) D g
In [HP12], it is shown that all M-adhesive categories are M, N -adhesive.
Lemma 1 (M-adhesive ⇒ M, N -adhesive). Let C be any category and N
be the class of all morphisms in C. Then C is M, N -adhesive if and only if C is
M-adhesive.
In the following, we give some examples of categories that are M, N -adhesive.
Lemma 2 (Basic M, N -adhesive Categories). The following categories are
M-adhesive [EEPT06b] and, by Lemma 1, M, N -adhesive where N is the class
of all morphisms in C:
1. The category Sets of sets and functions is M-adhesive where M is the class
of all injective functions.
2. The category Graphs of graphs and graph morphisms is M-adhesive where
M is the class of all injective graph morphisms.
3. The category LGraphs of labelled graphs and graph morphisms is M-
adhesive where M is the class of all injective graph morphisms.
The following category is M, N -adhesive, but not M-adhesive [HP12]:
4. The category PLGraphs of partially labelled graphs and graph morphisms
is M, N -adhesive where M and N are the classes of all injective and all
(injective) undefinedness-preserving1 graph morphisms, respectively.
3 Construction of Categories
There are various ways to construct new categories from given ones. Beside
the standard constructions (product, slice and coslice, functor and comma cat-
egory) we consider the constructions of a string category and a multiset cat-
egory. For each of these constructions, we prove a composition result, saying
1
A morphism f : G → H preserves undefinedness, if it maps unlabelled items in G to
unlabelled items in H.
more or less, whenever we start with Mi , Ni -adhesive categories, then the new
constructed category is M, N -adhesive for some M, N . For the definitions of
category-theoretic notions refer to [EEPT06b, Awo10].
First, we consider the standard constructions: product, slice and coslice, functor,
and comma category. For the definitions we refer to [EEPT06b] A2 and A6. Our
composition result generalizes the result from M- to M, N -adhesive categories.
Theorem 1 (Standard Constructions). M, N -adhesive categories can be
constructed as follows:
1. If Ci is Mi , Ni -adhesive (i = 1, 2), then the product category C1 × C2 is
M, N - adhesive where M = M1 × M2 and N = N1 × N2 .
2. If C is M, N -adhesive and X is an object of C, then the slice category
C\X and the coslice category X\C over X are M0 , N 0 -adhesive where the
morphism classes M0 , N 0 are restricted to the slice and coslice category, i.e.,
for X ∈ {M, N }, X 0 = X ∩ C\X and X 0 = X ∩ X\C, respectively.
3. If C is M, N -adhesive, then for every category X, the functor category [X, C]
is Mft , Nft -adhesive with functor transformations Mft and Nft .2
4. If Ci are Mi , Ni -adhesive and Fi : Ci → C functors (i = 1, 2), where F1 pre-
serves M1 , N1 -pushouts and F2 preserves M2 -pullbacks, then the comma
category ComCat(F1 , F2 , I) is Mc , N c -adhesive where Mc = (M1 ×M2 )∩
Mor, N c = (N1 × N2 ) ∩ Mor, and Mor is the set of all morphisms of the
comma category. We will use A ↓ B as a shorthand for the comma category
ComCat(A, B, I), with |I| = 1 and both functors A, B pointing into Sets.
Proof. The proof is a slight generalization of the corresponding one for M-
adhesive categories (see Theorem 4.15 in [EEPT06b]). In most cases the relevant
constructions can be done componentwise from objects or morphisms in the
original category. For the full proof see the long version [PH15]. 2
Second, we consider the constructions of a string and a multiset category and
prove that M, N -adhesive categories are closed under these constructions.
Construction (String Category). Given a category C, we construct a string
category C∗ as follows:
The objects are lists (finite sequences) A1 . . . Am of objects of C, including the
empty list λ. The morphisms between two objects A1 . . . Am and B1 . . . Bn (given
m ≤ n) are lists (finite sequences) of morphisms f1 : A1 → Bi . . . fm : Am →
Bi+m−1 in C, with B1 . . . Bi . . . Bi+m−1 . . . Bn for some 1 ≤ i ≤ m−n (i.e. A1 . . .
Am is embedded in B1 . . . Bn ). The empty list λ is an initial element for C∗ .
Our construction for a string category above is close to that of a free monoidal
category. Allowing for the existence of a morphism even if m < n, however
2
For a class X , Xft denotes the class of natural transformations t : F → G, where all
morphisms tX : F (X) → G(X) are in X .
contradicts these definitions and further prevents us from giving a workable
definition of a tensor product. We need these morphisms, especially in the case
of the multiset category below, to allow for the addition or removal of elements
in transformation systems based on these categories.
Construction (Multiset Category). Given a category C, we construct a
multiset category C⊕ as follows:
The object are lists (finite sequences) A1 . . . Am of objects of C, including an
empty list ∅. The morphisms between two objects A1 . . . Am and B1 . . . Bn (given
m ≤ n) are lists (finite sequences) of morphisms fi : Ai → Bji in C, where ji = jk
implies i = k, i ∈ {1, . . . , m}.In contrast to the above construction for a string
category, we ignore the order of elements.
We will use {|a, a, b|} to denote a multiset with elements a, a and b.
Theorem 2 (C M, N -adh ⇒ C∗ M∗ , N ∗ -adh, C⊕ M⊕ , N ⊕ -adh).
1. If C is M, N -adhesive, then the string category C∗ over C is M∗ , N ∗ -
adhesive where M∗ and N ∗ contain those morphisms which are lists of
morphisms in M and N , respectively. N ∗ is further restricted to morphisms
that perserve length, i.e. where domain and codomain are of equal length.
2. If C is M, N -adhesive, then the multiset category C⊕ over C is M⊕ , N ⊕ -
adhesive with M⊕ and N ⊕ contain those morphisms which are lists of mor-
phisms in M and N , respectively.
Proof. In both cases the relevant constructions can be done componentwise
from objects or morphisms in the original category and the composition and
decomposition properties can be inherited from morphisms in the underlying
category. The restriction of N ∗ to morphisms that preserve length ensures the
existence of pushouts. See the long version [PH15] for the full proof. 2
4 Partially Labelled Graphs
Let us reconsider the category PLGraphs of partially labelled graphs, investi-
gated e.g. in [HP02, HP12], where the labelling functions for nodes and edges are
allowed to be partial. In [HP12], it is shown that PLGraphs is not M-adhesive,
but M, N -adhesive if we choose M and N as the classes of all injective and all in-
jective, undefinedness-preserving graph morphisms, respectively. In this section,
we present an alternative proof of the statement: We show that the category
PLGraphs can be constructed from the category Graphs and a category PL
of labels by a multiset construction and the comma category construction.
First, we consider a label set L together with the symbol ⊥ indicating unde-
finedness. As morphisms we use all identities as well as all morphisms from ⊥
to a label in L.
Lemma 3 (PL is a Category). For each alphabet L, the class of all elements
in L ∪ {⊥}3 as objects and all morphisms of the form ⊥ → x and x → x
(x ∈ L ∪ {⊥}) forms the category PL where the composition of x → y and
y → z is x → z and the identity on x is x → x.
a b ... z
⊥
Proof. Follows directly from the definiton. 2
It can be shown that the category PL is M, N -adhesive.
Lemma 4 (PL is M, N -adhesive). The category PL is M, N -adhesive where
M and N are the classes of all morphisms and all identities, respectively.
Proof. We show the properties required in Definition 1, for pushouts and van
Kampen squares we can list the small number of cases exhaustively. See the long
version [PH15] for the full proof. 2
Partially labelled graphs generalize labelled graphs [Ehr79].
Definition 2 (PLGraphs). A partially labelled graph is a system G = (V, E, s,
t, l) consisting of finite sets V and E of nodes and edges, source and target
functions s, t : E → V , and a partial labelling function l : E + V → L 4 , where L
is a fixed set of labels.
A morphism g : G → H between graphs G and H consists of two functions
gV : VG → VH and gE : EG → EH that preserve sources, targets and labels, that
is, gE ; sH = sG ; gV , gE ; tH = tG ; gV , and lH (g(x)) = lG (x) for all x in Dom(lG ).
Fact 1. The class of partially labelled graphs and its morphisms constitute a
category PLGraphs, where morphism composition is function composition and
the identity is the identity function.
As an alternative to the existing proof we prove that the comma category of the
two functors Graphs : Graphs → Sets and P L : PL⊕ → Sets defined below is
M, N -adhesive. We further prove the category PLGraphs is isomorphic to this
comma category, thus PLGraphs is also M, N -adhesive. The isomorphism of
categories is defined as in Ehrig et. al. [EEPT06b].
3
We assume that ⊥ is not an element of L.
4
+ denotes the disjoint union of sets.
Definition 3 (Graphs : Graphs → Sets). The functor Graphs : Graphs →
Sets maps graphs to their underlying set of nodes and edges and is given as
follows: For a graph G0 = (V 0 , E 0 , s0 , t0 ), let Graphs(G0 ) = V 0 + E 0 and for a
graph morphism fG0 : A → B, let Graphs(fG0 ) be a natural transformation,
defined by Graphs(f )(x) = fV 0 (x) if x ∈ V 0 and fE 0 (x) otherwise.
Lemma 5. The functor Graphs : Graphs → Sets preserves M, N -pushouts,
where M is the class of injective graph morphisms, N is the class of all mor-
phisms.
Proof. See the long version [PH15]. 2
Definition 4 (P L : PL⊕ → Sets). The functor P L : PL⊕ → Sets maps
a multiset of labels to a set with distinct elements and S is given as follows:
For a multiset of labels m0 : L0 → N let P L(m) = l0 ∈L0 m̄(l0 ), where for
l0 ∈ L0 , m̄(l0 ) = {l10 , ..., lk0 } iff m(l0 ) = k. For a morphism f : m1 → m2 let
P L(f ) = P L(m1 ) → P L(m2 ) be a morphism in Sets, such that P L(f )(l10 ) = l20
iff P L(l1 ) = l10 , P L(l2 ) = l20 and f (l1 ) = l2 with l1 , l2 ∈ m1 , m2 respectively.
Lemma 6. The functor P L : PL⊕ → Sets preserves I-pullbacks, where I is
the class of all morphisms.
Proof. See the long version [PH15]. 2
For an object (G0 , m0 , op) of the comma category Graphs ↓ P L the morphism
op : Graphs(G0 ) → P L(m0 ) determines which node or edge is associated with
which label, i.e. op(e0 ) = li0 with e0 ∈ E 0 , l0 ∈ L0 and i ∈ N means the edge e0 is
labelled with l0 .
Lemma 7 (PLGraphs ∼ = Graphs ↓s P L). The category PLGraphs of par-
tially labelled graphs is isomorphic to the comma category Graphs ↓s P L, where
↓s indicates a restriction to surjective morphisms op in the comma category.
We restrict ourselves to those objects of the comma category where op is surjec-
tive, since there could otherwise be labels that are not associated with an object
in the graph.
Proof. The graph components of both categories are trivially isomorphic. It
remains to show that changes to a partial labelling function and a total labelling
function along with changes to the labels themselves can be employed towards
the same effect. For the proof see the long version [PH15]. 2
Now we are able to present an alternative proof of the fact that the category
PLGraphs of partially labelled graphs is M, N -adhesive. It is based on fact
that the categories Graphs of graphs and PL of labels are M, N -adhesive and
the constructions of a commutative monoidal category and the comma category
preserve M, N -adhesiveness.
Theorem 3 (PLGraphs is M, N -adhesive). The category PLGraphs of
partially labelled graphs is M, N -adhesive where M and N are the classes of all
injective and all injective, undefinedness-preserving graph morphisms, respec-
tively.
Proof. The new proof of Theorem 3 is illustrated in Figure 1.
1. By Lemmata 2 and 4, Graphs and PL are MG , NG and ML , NL -adhesive,
respectively. MG , NG are monomorphisms in Graphs and ML , NL are the
classes of all morphisms and all identity morphisms in PL, respectively.
2. By Theorem 2, PL⊕ is M⊕ , N ⊕ -adhesive.
3. By Theorem 1 and Lemmata 5 and 6, Graphs ↓s P L is Mc , N c -adhesive.
Note that Theorem 1 still holds for the restriction to a surjective op, since the
componentwise constructions can be still be done just as in the unrestricted
case.
4. By Lemma 7, PLGraphs is M, N -adhesive. Moreover M = F (Mc ) since
both of these classes include all monomorphisms and N = F (N c ) since the
perservation of undefinedness in N is analogous to the restriction to identity
morphisms in N L , which determines the treatment of labels in N c .
Graphs Lem 2 PL Lem 4
Thm 2
PL⊕
Thm 1
Graphs ↓s P L
∼
= Lem 7
PLGraphs
Fig. 1. Proof of “PLGraphs is M, N -adhesive”.
2
Example 1. Figure 2 shows a transformation rule for a partially labelled graph
consisting of a single node which is relabelled from a to b. Below the rule we
show objects of Graphs ↓ P L and their individual components. Note that, in
contrast to partially labelled graphs, we do not change the assigment of items
to labels but instead change the label itself.
a ⊥ b
Graphs
G = ({n1 }, ∅, s, t) {n1 } ... {n1 } ... {n1 }
op op op
PL PL PL
L = {|a|} {a1 } L = {|⊥|} {⊥1 } L = {|b|} {b1 }
Fig. 2. Example transformation of an object of Graphs ↓s P L
5 Attributed Graphs
Similiar to the construction for partially labelled graphs we construct attributed
graphs, where the attributes can be changed analogously to relabelling.
We start with defining a category where the objects collect all the attributes of
a node or an edge. These attribute collections consist of a set of names, each
of which is associated with a value. We use the category PL from section 4 to
represent these values.
Definition 5 (Att = IDSets ↓ P L). The category Att of attribute collections is
defined as the comma category IDSets ↓ P L where IDSets denotes the identity
functor over Sets.
Lemma 8 (Att is Mc , N c -adhesive). The category Att of attribute collec-
tions is Mc , N c -adhesive where Mc , N c are the classes of morphisms induced
by the comma category construction.
Proof. The proof is illustrated in Figure 3. IDSets ↓ P L is Mc , N c -adhesive,
since Sets and PL are M, N -adhesive and a multiset and comma category
construction preserve M, N -adhesiveness. 2
To construct attributed graphs we define a functor from multisets of these at-
tribute collections to sets for later use in the comma category construction (com-
pare with the construction for partially labelled graphs in section 4). We also
prove that this functor preserves pullbacks, since this is required for the comma
category to preserve M, N -adhesiveness.
Definition 6 (Att : Att⊕ → Sets). The functor Att : Att⊕ → Sets that maps
attribute collections to sets with distinct values is given by the following: A
triple (IDSets (S), P L(m), op)⊕ is mapped to the set S ⊕ + P L(m)⊕ where ⊕
is flattened analogously to the way P L does (see Definition 4). A morphism
f : A → B in Att⊕ is mapped to a morphism Att(f ) : Att(A) → Att(B), where
elements in Att(A) are mapped to elements in Att(B) based on the original
mappings in Att⊕ .
Sets Lem 2 PL Lem 4
Thm 2
PL⊕
Thm 1
IDSets ↓ P L
= Def 5
Att
Fig. 3. Proof of “Att is Mc , N c -adhesive”.
Lemma 9 (Att preserves I-pullbacks). The functor Att : Att⊕ → Sets
preserves I-pullbacks where I is the class of all morphisms.
Proof. See the long version [PH15]. 2
Example 2. Figure 4 shows a transformation rule in Att. The attribute col-
lection consists of a single attribute a, which has its value changed from 5 to
9 by the rule. Below the rule we show the objects of Att with their individual
components.
a=5 a=⊥ a=9
IDSets
N = {a} {a} ... {a} ... {a}
op op op
PL PL PL
V = {|5|} {51 } V = {|⊥|} {⊥1 } V = {|9|} {91 }
Fig. 4. Example transformation rule for objects of Att
Definition 7 (AttGraphs = Graphs ↓ Att)). The category AttGraphs of
attributed graphs is defined as the comma category Graphs ↓ Att.
Now we are able to show that the category AttGraphs of attributed graphs is
M, N -adhesive. It is based on the fact that the categories Graphs of graphs
and Att of attribute collections are M, N -adhesive and the constructions of a
multiset category and a comma category preserve M, N -adhesiveness.
Theorem 4 (AttGraphs is M, N -adhesive). The category AttGraphs of at-
tributed graphs is Mc , N c -adhesive where Mc , N c are the classes of morphisms
induced by the comma category construction.
Proof. The proof is illustrated in Figure 5.
1. By Lemmata 2 and 8, Graphs and Att are MG , NG and MA , NA -adhesive,
respectively. MG , NG are monomorphisms in Graphs and MA , NA are the
classes of morphisms induced by the comma category construction of Att.
2. By Theorem 2, Att⊕ is M⊕ , N ⊕ -adhesive.
3. By Theorem 1 and Lemmata 5 and 9, Graphs ↓ Att is Mc , N c -adhesive.
4. By Defintion 7, AttGraphs is Mc , N c -adhesive.
Graphs Lem 2 Att Lem 8
Thm 2
Att⊕
Thm 1
Graphs ↓ Att
= Def 7
AttGraphs
Fig. 5. Proof of “AttGraphs is Mc , N c -adhesive”.
2
In the following we briefly compare these attributed graphs to some existing
attribution concepts. In contrast to the typed attributed graphs in [EEPT06b]
these attributed graphs can have at most one value for an attribute. We con-
structed untyped graphs and even the attributes themselves have no types. Using
the construction for the slice category from Theorem 1 we can build graphs where
typing is done at either level, which allows us to have typed attributes on an
untyped graphs, such that attribute values are constrained by the type but what
attributes a node or edge has is not. In contrast typed attributed graphs require
that the graph is typed and thus do not allow e.g. the addition of attributes
to a node or edge. Compared to the attribution concepts used in [Plu09] we do
not require a seperate instantiation of a rule schema and it is possible to find a
match without fully specifying other, pontentially uninteresting, attributes. We
do not, however base our attributes on an algebra that would allow us to per-
form some computations on the attributes, this would require additional work
to prove M, N -adhesiveness for a suitable category. Fortunately we only need to
provide this proof for such attributes once, enabling us to construct many differ-
ent attributed structures without concerning ourselves with e.g. the underlying
graphs.
6 W-adhesive Categories
The concept of M, N -adhesive categories [HP12] was introduced as a frame-
work for partially labeled graphs. More or less at the same time, the concept
of W-adhesive categories was introduced by Golas [Gol12] as a framework for
attributed graphs. In this section, we present a precise relationship between
M, N -adhesive and W-adhesive categories.
We obtain the following relationship between M, N - and W-adhesive categories.
Theorem 5 (M, N -adhesive ⇒ W-adhesive). If the category C is M, N -
adhesive, then the tuple (C, M, M, M × N ) is a W-adhesive category. Vice
versa, if the tuple (C, R, M, W) is W-adhesive, then C is R, Ran(W)-adhesive
provided that the range Ran(W) of W is stable under pushout and pullback and
contains all isomorphisms.
Proof. We can directly derive the properties of W-adhesive categories from the
definition of M, N -adhesive categories and vice versa, except for the stability of
the morphism classes M, N over pushouts and pullbacks. Due to the required
properties of W-adhesive categories, the class of W-spans used necessarily equals
the spans defined by R × N thus allowing us to bridge the different definitions.
For the proof see the long version [PH15]. 2
Remark. The situation may be summarized as follows:
– The requirements for an M, N -adhesive category are slightly more strict
than those for W-adhesive categories.
– For M, N -adhesive systems, the Local Church-Rosser Theorem, the Paral-
lelism Theorem, and the Concurrency Theorem are proven. For W-adhesive
systems, up to our knowledge, there has only been a proof of (part of) the
Local Church-Rosser Theorem.
– The W-adhesive categories of attributed objects in [Gol12] are M, N -ad-
hesive: N is the class of ⊥-preserving morphisms, contains all isomorphisms
and is stable under pushout and pullbacks.
7 Related Concepts
Throughout the literature, various versions of adhesive and quasiadhesive [LS05],
weak adhesive HLR [EHPP06], partial map adhesive [Hei10], and M-adhesive
[EGH10] exist. In [EGH10], all these categories are shown to be also M-adhesive
ones. The categories of labelled graphs, typed graphs, and typed attributed
graphs in [EEPT06b], are known to be M-adhesive categories if one chooses
M to be the class of injective graph morphisms [EGH10]. Each such category
induces a class of M-adhesive systems for which several classical results of the
double-pushout approach hold.
Unfortunately, the framework of M-adhesive systems does not cover graph trans-
formation with relabelling. In [HP12], the authors generalize M-adhesive cate-
gories to M, N -adhesive categories, where N is a class of morphisms containing
the vertical morphisms in double-pushouts, and show that the category of par-
tially labelled graphs is M, N -adhesive, where M and N are the classes of injec-
tive and injective, undefinedness-preserving graph morphisms, respectively. In-
dependently, Golas [Gol12] provided a general framework for attributed objects,
so-called W-adhesive systems which allows undefined attributes in the interface
of a rule to change attributes, which is similar to relabelling. By Lemma 1 and
Theorem 5, the hierarchy of adhesive categories in [EGH10] can be extended in
the following way:
⇒ ⇒ ⇒ ⇒
adhesive adhesive HLR M-adhesive M, N -adhesive W-adhesive
6⇐ 6⇐ 6⇐ 6⇐
In the literature, there are several variants of attribution concepts, e.g., Löwe
et al. [LKW93] view graphs as a special case of algebras. These algebras can
then additionally specify types for attributes. Ehrig et al. [EEPT06a] — intro-
duce typed attributed graphs, expanding the graph by including an algebra for
attribute values. To facilitate attribution, typed attributed graphs extend graphs
by attribution nodes and attribution edges. All possible data values of the al-
gebra are assumed to be part of the graph. Nodes and edges are attributed by
adding an attribution edge that leads to an attribution node. Kastenberg and
Rensink [KR12] take a similar approach, but instead of only encoding the data
values, operations and constants are also included in the graph. Plump et al
[Plu09] use a different approach to attribution. Here labels are replaced by se-
quences of attributes. Rules are complemented by rule schemata in which terms
over the attributes are specified. These variables are substituted with attribute
values and evaluated during rule application. Instead of modifying the definition
of graphs and graph transformations to include attributes, Golas [Gol12] defines
an attribution concept over arbitrary categories. Duval et al. [DEPR14] allow
attributed graphs and allow rules to change attributes.
In [Peu13], Peuser compares the approaches of Ehrig et al. [EEPT06a] and Plump
[Plu09] and introduces a useful new concept of attribution which is the basis of
this work.
The idea of composition of adhesive categories is not new: For M-adhesive cat-
egories, the standard constructions of product, slice and coslice, functor, and
comma categories are given in [EEPT06b].
8 Conclusion
In this paper, we have continued the work on M, N -adhesive categories and have
presented several examples (see Table 1).
category structures adhesiveness reference
Sets sets M-adh [EEPT06b]
PL sets of labels M, N -adh Lemma 4
Att attribute collections M, N -adh Lemma 8
Graphs unlabelled graphs M-adh [EEPT06b]
LGraphs labelled graphs M-adh [Ehr79]
PLGraphs partially labelled graphs M, N -adh [HP12], Thm 3
AttGraphs attributed graphs M, N -adh Theorem 4
Table 1. Examples of M, N -adhesive categories
The main contributions of the paper are the following:
(1) Closure results for M, N -adhesive categories.
(2) A new, shorter proof of the result in [HP12] that the category of partially
labeled graphs is M, N -adhesive.
(3) A new concept of attributed graphs together with a proof that the category
of these attributed graphs is M, N -adhesive and an application to transfor-
mation systems saying that for these attributed graphs, the Local Church-
Rosser Theorem, the Parallelism Theorem and the Concurrency Theorem
hold provided that the HLR+ -properties are satisfied.
Further topics might be:
(1) Investigate the relationship to the approach of Parisi-Presicce et al. [PEM87]
considering graphs with a structured alphabet.
(2) Proof of the HLR+ -properties for the category AttGraphs to obtain the Lo-
cal Church-Rosser Theorem, the Parallelism Theorem and the Concurrency
Theorem for this type of attributed graphs.
(3) Generalization of the approach to systems with so-called left-linear rules,
i.e., rules where only the left morphism of the rule is required to be in M
as, e.g., in [BGS11].
Acknowledgements. We would like to thank the anonymous referees and
Wolfram Kahl for helpful feedback on an early version of this paper.
References
Awo10. Steve Awodey. Category Theory. Oxford University Press, 2010.
BGS11. Paolo Baldan, Fabio Gadducci, and Pawel Sobociński. Adhesivity is not
enough: Local Church-Rosser revisited. In Mathematical Foundations of
Computer Science (MFCS 2011), volume 6907 of Lecture Notes in Com-
puter Science, pages 48–59, 2011.
DEPR14. Dominique Duval, Rachid Echahed, Frederic Prost, and Leila Ribeiro.
Transformation of attributed structures with cloning. In Fundamental Ap-
proaches to Software Engineering, volume 8411 of Lecture Notes in Com-
puter Science, pages 310–324, 2014.
EEKR99. Hartmut Ehrig, Gregor Engels, Hans-Jörg Kreowski, and Grzegorz Rozen-
berg, editors. Handbook of Graph Grammars and Computing by Graph
Transformation, volume 2: Applications, Languages and Tools. World Sci-
entific, 1999.
EEPT06a. Hartmut Ehrig, Karsten Ehrig, Ulrike Prange, and Gabriele Taentzer. Fun-
damental theory of typed attributed graph transformation based on adhes-
ive HLR categories. Fundamenta Informaticae, 74(1):31–61, 2006.
EEPT06b. Hartmut Ehrig, Karsten Ehrig, Ulrike Prange, and Gabriele Taentzer. Fun-
damentals of Algebraic Graph Transformation. EATCS Monographs of
Theoretical Computer Science. Springer, 2006.
EGH10. Hartmut Ehrig, Ulrike Golas, and Frank Hermann. Categorical Frameworks
for Graph Transformation and HLR Systems based on the DPO Approach.
Bulletin of the EATCS, 112:111–121, 2010.
EHKP91. Hartmut Ehrig, Annegret Habel, Hans-Jörg Kreowski, and Francesco
Parisi- Presicce. From graph grammars to high level replacement systems.
In Graph Grammars and Their Application to Computer Science, volume
532 of Lecture Notes in Computer Science, pages 269–291, 1991.
EHPP06. Hartmut Ehrig, Annegret Habel, Julia Padberg, and Ulrike Prange. Adhes-
ive high-level replacement systems: A new categorical framework for graph
transformation. Fundamenta Informaticae, 74(1):1–29, 2006.
Ehr79. Hartmut Ehrig. Introduction to the Algebraic Theory of Graph Gram-
mars. In Graph-Grammars and Their Application to Computer Science
and Biology, volume 73 of Lecture Notes in Computer Science, pages 1–69,
1979.
EKMR99. Hartmut Ehrig, Hans-Jörg Kreowski, Ugo Montanari, and Grzegorz Rozen-
berg, editors. Handbook of Graph Grammars and Computing by Graph
Transformation, volume 3: Concurrency, Parallelism, and Distribution.
World Scientific, 1999.
Gol12. Ulrike Golas. A General Attribution Concept for Models in M-adhesive
Transformation Systems. In Graph Transformations (ICGT’12), volume
7562 of Lecture Notes in Computer Science, pages 187–202, 2012.
Hei10. Tobias Heindel. Hereditary pushouts reconsidered. In Graph Transforma-
tions (ICGT 2010), volume 6372 of Lecture Notes in Computer Science,
pages 250–265, 2010.
HP02. Annegret Habel and Detlef Plump. Relabelling in Graph Transformation.
In Graph Transformation (ICGT 2002), volume 2505 of Lecture Notes in
Computer Science, pages 135–147, 2002.
HP12. Annegret Habel and Detlef Plump. M, N -adhesive Transformation Sys-
tems. In Graph Transformations (ICGT 2012), volume 7562 of Lecture
Notes in Computer Science, pages 218–233, 2012. Long version avail-
able at: http://formale-sprachen.informatik.uni-oldenburg.de/pub/
index.html.
KR12. Harmen Kastenberg and Arend Rensink. Graph attribution through sub-
graphs. Technical Report TR-CTIT-12-27, University of Twente, 2012.
LKW93. Michael Löwe, Martin Korff, and Annika Wagner. An algebraic framework
for the transformation of attributed graphs. In Term Graph Rewriting:
Theory and Practice, pages 185–199. John Wiley, 1993.
LS05. Stephen Lack and Pawel Sobociński. Adhesive and quasiadhesive cate-
gories. Theoretical Informatics and Application, 39(2):511–546, 2005.
PEM87. Francesco Parisi-Presicce, Hartmut Ehrig, and Ugo Montanari. Graph
rewriting with unification and composition. In Graph Grammars and Their
Application to Computer Science, volume 291 of Lecture Notes in Computer
Science, pages 496–514, 1987.
Peu13. Christoph Peuser. Attribution Concepts for Graph Transformation. Mas-
ter’s thesis, 2013. Available at: http://formale-sprachen.informatik.
uni-oldenburg.de/pub/index.html.
PH15. Christoph Peuser and Annegret Habel. Attribution of graphs by
composition of M, N -adhesive categories: Long version. Available
at: http://formale-sprachen.informatik.uni-oldenburg.de/~skript/
fs-pub/PH15_mn-composition_long.pdf, 2015.
Plu09. Detlef Plump. The graph programming language GP. In Proc. Algebraic
Informatics (CAI 2009), volume 5725 of Lecture Notes in Computer Sci-
ence, pages 299–122, 2009.
Roz97. Grzegorz Rozenberg, editor. Handbook of Graph Grammars and Computing
by Graph Transformation, volume 1: Foundations. World Scientific, 1997.