In this paper, we consider Global Graph Transformations where all occurrences of a set of prede ned local rules are applied altogether synchronously so that each part of the original graph gives rise to a part of the result graph, without any reference to the original one. The particularity here is that our framework is deterministic. This is achieved by incorporating a notion of mutual agreement between its local rules. Our proposition is rst motivated and illustrated on existing problems coming from di erent domains. It is then formalized as a categorical construction which is nally compared to more usual algebraic constructions, in particular to the strongly related Amalgamation Theorem. Applications of this work include the generalization of cellular automata and the clari cation of some frameworks of complex systems modeling where the usual mutual exclusion of rule applications can be replaced by a concept of mutual agreement.
The framework proposed herein has been designed with the need to model deterministic dynamical systems by graph transformations. The state of such a system is represented by a graph and its global dynamics is speci ed through a set of local evolution rules.
One such example is the simple framework of cellular automata (CA). The
state of a CA is usually represented by a labeled regular graph where the nodes
are the cells, the labels encode the cell states, and the edges represent the
neighborhood relation between cells. A global evolution step consists of a synchronous
update of all the labels relying on a local evolution function, the structure of the
graph remaining unchanged. From another point of view, each patch of neighbor
cells (e.g. triple of consecutive cells in 1D CA with radius 1, square of 9 cells in
2D Moore CA) gives rise to a new node with the updated label. All these new
nodes are then connected together to form the next state graph representation
which is independent from the current one. Recently, di erent formalizations
based on this point of view have been proposed to generalize CA to arbitrary
graphs with dynamic structures [
Other work was already devoted to the simulation of the so called Dynamical
Systems with Dynamical Structure [
As a result of these two motivations, the transition mechanism of the modeled
system is described in our setting by a set of rules that do not send rooted
graphs to nodes as in CA, nor nodes to graphs as it is often the case in graph
transformation [
The proposed framework reminds some existing ones. The statement of the
coherence above is the same leading to the concept of sub-rule and amalgamation
in the double-pushout approach [
In this section, we describe brie y existing approaches of parallel rewriting systems with a nal comparison to global transformations.
One of the rst parallel rewriting systems are Lindenmayer Systems (LS), which are parallel string rewriting in contrast with sequential Chomsky grammars. A hk; li LS (k; l 2 N) is a context-sensitive system gathering productions in a transition table, so that each sub-word of length k + 1 + l (i.e., a letter with a left context of length k and a right context of length l1) is associated with (possibly many) words. The parallel rewriting of a word is done as follows: each letter is substituted accordingly to its left and right contexts by one of its associated words in the transition table. Obviously, the LS is deterministic if the transition table is a function (i.e., associates a unique word with each entry). LS have been extensively studied for their expressive powers and compared to the classic Chomsky hierarchy of formal languages [19]. They have also been used in the modeling of unidimensional and tree-like dynamical systems [16]. LS can be seen as a special case of parallel graph transformation, restricted to linear/sequential graphs. Other special cases of graphs can be addressed. For example, Paun Systems (roughly speaking, nested parallel multiset rewriting systems [15]) can be considered as complete graph transformations. Such systems derive naturally from LS by considering rewriting modulo associativity and commutativity: any two symbols of a string representing a multiset can be made neighbors by permuting the letters of the word. In this setting, a production is a metaphor of a chemical reaction. The left hand side (l.h.s.) of a production designates a sub-multiset which is entirely replaced by its associated right hand side (r.h.s.) (in contrast with LS where each letter is replaced independently). To avoid the consumption of the same symbol by two di erent reactions, the maximal-parallel strategy is considered leading to non-determinism.
Extension of LS to arbitrary graph transformation is not an easy task [
e3 c2 c3
The previous examples are set-theoretic approaches: graph transformations
are expressed in terms of sets and set operations. Graph transformations can also
be represented algebraically using the double-pushout and the simple-pushout
approaches which formalize the idea of local replacement in a categorical
manner [18]. The double-pushout approach is inherently local so that it needs to
be extended to deal with parallel applications leading to the concepts of
parallelism [
Since the present article follows naturally work introduced in [20], we consider
cell complexes, a more general setting than graphs. Like a graph, a cell complex
is a formal construction that builds a space in a combinatorial way through more
basic objects called topological cells. Each topological cell abstractly represents
a part of the whole and is characterized by a natural integer called dimension. A
topological cell of dimension d is called d-cell. The structure of the whole space,
corresponding to the partition into topological cells, is considered through the
incidence relationships, relating two \neighbor" cells in the partition. A graph
can then be seen as a cell complex composed of 0-cells and 1-cells, respectively
the nodes and the edges, so that the incidence relationship of the complex
coincides with the usual notion of incidence in graphs. More generally, a cell complex
using only two dimensions is an undirected multi- and hyper-graph. There exist
many possible formal de nitions of cell complexes coming from di erent elds
(algebraic topology [
Let L be an arbitrary set of symbols. A labeled abstract cell complex K with labels in L is given by a tuple hCK; K; dimK; lKi where CK is the set of abstract topological cells, K is a locally nite2 strict partial order relation over CK, dimK : hCK; Ki ! hN; <i is a strictly monotonic map assigning the dimension to each cell, and lK : CK ! L is a map assigning a label to each cell. An example of an abstract cell complex is shown on Fig. 1. We denote Acc the set of abstract cell complexes. In the following, we use the term cell complex (resp. cell ) for abstract cell complex (resp. topological cell) since there is no possible ambiguity.
A cell complex morphism h : K ! K0 from a cell complex K to a cell complex K0 is given by a strictly monotonic map Ch : hCK; Ki ! hCK0 ; K0 i such that lK = lK0 Ch, and dimK = dimK0 Ch. A cell complex inclusion i : K ! K0 from a cell complex K to a cell complex K0 is a cell complex morphism from K to K0 such that Ch is injective.
We consider the category AccML of cell complexes and cell complex
morphisms between them on one hand, and the sub-category AccIL of cell complexes
and cell complex inclusions between them on the other hand, together with the
associated inclusion functor UL : AccIL ! AccML. In the following, the
subscript L is omitted, the set of labels is clear from the context and we never
consider di erent sets of labels simultaneously. For the categorical discussion,
we use the concepts of categories, functors, natural transformations, pushouts,
colimits and comma categories. For formal de nitions of these concepts, we refer
to [
Mesh re nement is an approach used in geometrical modeling to generate smooth
surfaces from an initial set of control points. Mesh re nement algorithms
consist generally in iteratively generating new control points from current ones by
applying a set of creation rules. Such procedures are commonly used in
numerical resolution schemes and can be speci ed through graph transformations [
Although mesh algorithms are intuitively described by local graphical schemes,
they operate on the whole mesh and then turn out to be global and synchronous.
Let us illustrate this issue by considering the Loop subdivision procedure [
For the sake of illustration, let us consider that the re nement is restricted to a sub-part of the mesh. The region is speci ed by white or black labeled nodes so that the subdivision only occurs on triangles incident to three black nodes. Solutions exist to stop the natural propagation of the procedure over the whole mesh. Here, we consider an additional rule (see Fig. 2b) which deals with triangles located on the boundary of the region to be re ned, i.e., incident to exactly two black nodes. Other triangles are left unchanged.
The use of dashed contexts in Fig 2 is not accurate. Let us design a complete set of rules allowing the re nement of a triangular mesh in one global step. As a starting point, we specify the transformation of any single triangle of the mesh by considering two subdivision rules, 1 and 2 (corresponding to Fig. 2 without dashed context), and two more additional rules, 3 and 4, for unmodi ed triangles. These rules are shown on top of Fig. 3a.
Obviously, there is a lack of speci cation since connections between triangles are not taken into account. For instance, let us consider two triangles with only black nodes connected by a common edge as shown on the left of Fig. 4. Two matchings of the l.h.s. of rule 1 are clearly identi ed. Therefore, the resulting cell complex should be composed of two instances of the r.h.s. of rule 1. However, nothing speci es the way to built it. Forgetting mesh re nement for a moment, many possible constructions are conceivable: leaving the r.h.s. instances isolated, (a) Local Transformation Rules
(b) Inclusion between Rules 8 9 or merging them by a vertex or an edge, or even identifying them in only one instance, and so on and so forth.
In the case of mesh re nement, when two triangles share an edge, the two corresponding edges on the r.h.s. should also be shared on the resulting cell complex. There are two ways to specify such a behavior: one union-based method where a super-rule is designed for pairs of triangles, and another dual intersection-based method where an agreement is given about the transformation of the common edge. Here, we choose the latter method focusing on the evolution of an edge incident to two black nodes. Two things are required: rstly rule 5 of Fig. 3a speci es the subdivision of that edge; secondly for each edge found on the l.h.s. of rule 1, the associated divided edge is identi ed in the r.h.s. of 1 as shown on Fig. 3b.
With this information at hand, the previous example of two side-by-side triangles is clari ed: there are two matchings of 1 and one matching of 5 included in the two former matchings. The result cell complex is the unique cell complex where we can see two instances of the r.h.s. of 1 and one instance of the r.h.s. of 5 with inclusions between them being exactly the ones dictated by the inclusion rule. This can be observed in Fig. 4 where the inclusions between the l.h.s. matchings and the correspondence with the associated r.h.s. inclusions between the corresponding r.h.s. instances are depicted.
Iterating this design process for all possible intersections between rules, we obtain all the rules of Fig. 3a and all the inclusions given in Fig. 3b. Rules 6 and 7 describe the conservation of edges incident to a white node and the conservation of nodes is speci ed in 8 and 9. The latter are necessary for triangles sharing only one node. After transformation, their r.h.s. must also be connected by a node3. 3 As a byproduct of this intersection-based methodology, rules 5- 9 are used to manage isolated edges and nodes, which seems coherent with the re nement process. If these e ects are not desired then the union-based methodology is applicable, leading to more transformation rules, namely 32 pair-rules since there are 4 types of triangles and two triangles are either incident by an edge or a node. This allows to stay strictly concerned with triangles.
(a) (b) (c) (d)
As for the rule 5, all inclusions between the l.h.s.'s of these new rules are found and the associated r.h.s.'s are identi ed. This association of inclusion has to be seen as a set of rules too, that we call inclusion rules : for each inclusion of one l.h.s. in another l.h.s., an inclusion rule speci es an associated inclusion between the two corresponding r.h.s. Put in another way, theses inclusion rules express a kind of mutual agreement between the rules. When a rule indicates a transformation on a l.h.s., and this l.h.s. includes the l.h.s. of another rule, the former rule must achieve the transformation required by the latter rule, and this is materialized by an inclusion rule indicating where this required transformation can be found. So no mutual exclusion is necessary. This is reminiscent of the notion of sub-production in amalgamation. The comparison with this concept is delayed to Sect. 5.3. The construction procedure described above about the transformation of two side-by-side triangles can be generalized to any mesh as follows: 1. Pattern matching (Fig. 5a ) 5b): the original mesh is split into all the matchings of the local rules l.h.s. together with all the inclusion information between these matchings. Any unmatched part of the mesh is lost. 2. Local rule application (Fig. 5b ) 5c): each l.h.s. instance is locally replaced by its corresponding r.h.s. The inclusion information is also updated: each l.h.s. inclusion is replaced by its corresponding r.h.s. inclusion. 3. Reconstruction (Fig. 5c ) 5d): the inclusion information are nally used to merge the di erent r.h.s. giving rise to the transformed mesh.
Fig. 5 illustrates the computation of a global transformation step on a mesh composed of four triangles. Note that Figs. 5b and 5c only show more explicitly for the four-triangles case the inclusion structures already described in Fig. 4 for the two-triangles case.
This construction of the polyhedral subdivision based on mutual agreement has to be compared with the equivalent construction in [20] using mutual exclusion. Mutual exclusion prevents the computation of re nement in one global step. The solution of [20] consists of a two-step procedure: a rst transformation focuses on the subdivision of all edges and a second transformation splits the obtained hexagons and squares into triangles. Exclusion holds since the l.h.s. of each rule consists of only one element (a 1-cell for the rst step, a 2-cell for the second step). Obviously the results of both approaches are the same. However the exclusion based approach su ers from two main drawbacks: 1. A marking is required in the facets subdivision step to identify the nodes generated by the edge subdivision step. For example, in the substitution of an hexagon by four triangles, the three newly created edges surrounding the central triangle are incident to new nodes. 2. The intermediate cell complex contains hexagons and squares and then is not a regular triangular mesh. An implementation of this approach requires the use of a data structure allowing the representation of such a complex. This is beyond the ability of data structures classically used in geometric modeling which strongly rely on the triangular nature of the meshes. 5
In this section, we begin by formalizing the constructions described in the example using categorical concepts. Then, we compare the double-pushout (DPO) approach and global transformations, showing in particular some correspondence in the particular case where some conservation rules are speci ed. We also compare global transformations to the Amalgamation Theorem. The similarity is explained, and some di erences are identi ed. 5.1
Here, we want to give a formal speci cation of the objects and constructions presented in Section 4. A transformation rule is a pair of two cell complexes, the l.h.s. and the r.h.s. A set of transformation rules gives rise to a function R0 : L0 ! Acc, where L0 Acc denotes the set of l.h.s., that maps each l.h.s. to its corresponding r.h.s. An inclusion rule between two transformation rules and 0 associates an inclusion of the l.h.s. of 0 in the l.h.s. of with an inclusion of the r.h.s. of 0 in the r.h.s. of . Let us denote L1 the set of all inclusions between any pair of l.h.s. of L0, the set of inclusion rules can be interpreted as a function R1 mapping any element of L1 to its corresponding inclusion in Acc. A set of inclusion rules is said to be complete if the associated function is total. A set of inclusion rules is said to be consistent if all the inclusions agree on composition. In that sense, the set of inclusion rule given in Fig. 3b for the mesh re nement example is complete and consistent4. It is trivial to see that these two properties induce the determinism of a global transformation since any case that could be encountered is taken into account by a mutual agreement (completeness) and there is no contradiction between these agreements (consistency).
This situation can be nicely summarized in terms of categorical concepts. Considering that L0 and L1 form a sub-category L of the category AccI, R0 and R1 form a functor R from L to AccI. While consistency holds since R, as a functor, respects the morphism composition in AccI, completeness is grabbed when L is a full sub-category where all possible inclusions are considered. This leads to the following de nition:
by a tuple hLT ; LT ; RT i where LT is a full subcategory of AccI corresponding to the l.h.s. with LT : LT ! AccI its associated inclusion functor and RT : LT ! AccI is a functor from LT to AccI.
We now formalize how a global transformation T is applied on a cell complex K to build the associated result T K. Following the decomposition presented in Section 4.2, we get: 1. Pattern matching : all the matchings of the l.h.s. of T in K and the way they are included one in each other exactly correspond to the objects and morphisms of the comma category LT =K. Objects of LT =K are pairs hl 2 LT ; i : LT l ! Ki where l is a l.h.s. and i an inclusion of this l.h.s. in K. Morphisms of the comma category are inclusions between the matchings, i.e., a morphism from a matching hl; ii to a matching hl0; i0i is an inclusion j : l ! l0 in L such that i = i0 LT j. 2. Local rule application: in order to get the r.h.s. corresponding to each matching, we rst use the projection functor ProjLT =K : LT =K ! LT de ned on matchings as ProjLT =K = hl; ii 7! l, and on matching inclusions as ProjLT =K = j 7! j. The functor RT then maps each l.h.s. to the corresponding r.h.s., and each l.h.s. inclusion to the corresponding r.h.s. inclusion. So the result of this step is the compound functor RT ProjLT =K. 3. Reconstruction: all the r.h.s. instances are nally glued together w.r.t. RT ProjLT =K. The resulting cell complex T K could be obtained as the colimit of this functor. However, colimits are only guaranteed5 in AccM since the universality may require a non-inclusion morphism to hold. So we use the forgetful functor U to pass from AccI to AccM. 4 Only a subset of the inclusion rules is drawn but all other rules can be retrieved using composition of inclusion. 5 A way to show that all the colimits exist consists in exhibiting an initial object and all pushouts. Here, the initial object is simply the empty cell complex. The pushout of a span of cell complexes can be obtained from the pushout in Set of their cells sets by adding the unique possible dimension function and the smallest possible strict partial order relation, which happens to necessarily exist thanks to the dimensions.
A global transformation application is summarized as follows:
plex K and a global transformation T , the result T K of the application of T on K is the cell complex T K = Colim(U RT ProjLT =K).
Note that since we consider all the inclusions between the l.h.s. graphs, we also consider their automorphisms, i.e., their symmetries. This means that, in our previous examples, each matching is really matched as many times as it has symmetries. The nal result remains correct because all the results of these symmetric matchings are glued together appropriately due to the functorial nature of LT and RT . Considering these automorphisms is in fact meaningful as they allow to prevent incoherent speci cations that intuitively lead to symmetry breaking. Unfortunately, the size of this paper does not allow us to enter into a more detailed discussion about these features. 5.2
One of the consequences of our construction of the transformation result is that all parts of the original cell complex which are not matched are not conserved by any means. This is why we do not consider any morphism relating l.h.s. and r.h.s. If something has to be kept, this must be speci ed explicitly as we did for the not-re ned triangles in Section 4. This is in plain contrast with the DPO approach where the default behavior is to conserve unmatched parts of the graph and deletion has to be speci ed explicitly.
However, if a global transformation states that some patterns have to be conserved, then it is possible to see the elements of the DPO occurring in a di erent light. This relation appears because conservation rules have identical l.h.s. and r.h.s. So despite the fact that all considered inclusions are either strictly between l.h.s. or strictly between r.h.s., these conservation rule allows to think inclusions linking both l.h.s. and r.h.s. worlds. To express this a bit more visually, let us consider a derivation G ) G0 via a production p = L K ! R based on an inclusion i : L ! G and try to lay it out in a global transformation application way. The elements of the derivation are given in the following diagram. i L G l l0
K k G r r0
R o G0 In the global transformation framework, G is a compound of many conservation rules, K is a compound of many small conservation rules included in both the conserved and the modi ed parts, and L and R are all the l.h.s. and r.h.s. of the transformation rules. The result G0 is obtained as the colimit of K, G and R, which is precisely a pushout. This gives the following layout: k
K l G
L rules
K
k G
r R matchings
K r.h.s. and colimit
K k l G
L i l l0 i
G
k r G
R o r r0 o
Notice that no notion of pushout complement is required in our construction. The existence of a pushout complement for a production L K ! R based on a morphism m : L ! K imposes that the parts of L which are not in K should not be incident to any cell outside of m for a derivation to be feasible. Contrary to DPOs, all matchings are necessarily applicable in our setting. This gives more exibility in the design of transformation rules and allows to work exclusively with inclusions. All of this are consequences of the fact that we are in the restricted case where nothing from an input cell complex is considered as conserved.
There is a strong relation between the proposed formalism and the amalgamation of productions available in the DPO approach. Indeed, both consider rules and a notion of inclusions between rules. Moreover, amalgamation of two productions via a sub-production is a pushout of productions and it is well-known that a colimit can be viewed as being mainly a compound of pushouts. If we consider all the matchings of a set of productions and if we have enough subproductions to handle all possible overlaps, it is clearly possible to synchronize all the productions into one production that operates in a single step as required.
However there are some di erences. We have already discussed the default behavior on the unmatched part for both approaches: amalgamation conserves it while global transformation drops it. Assuming that there is no unmatched part, a strong di erence remains because of applicability. Indeed, in the DPO approach the amalgamation theorem states that anytime an amalgamation of productions can be applied, each production can be applied individually, with the restriction imposed by the existence of a pushout complement explained earlier. Let us consider the following production that is a straightforward translation of rule 1 of Fig 3a: Since the three 1-cells in L are not part of K, the rule can only be used on triangles whose edges are incident to no other 0-cells nor 2-cells, which is not the common case in a triangular mesh. Indeed, in mesh re nement, every cells (except the 0-cells) have to be transformed and the main part of them are incident to each other. This makes impossible in general the design of productions isolating the cells to be transformed, except by considering the whole black region in one global production. As a consequence, there is no simple way to use amalgamation alone to build a single global production from many local ones.
Again, an important property of our approach is that there is no applicability condition over the cell complex to transform. The only constraint comes from the completeness and the consistency of the set of inclusion rules which ensure to get a well de ned and unique result. 6
In this article, we have presented the Global Graph Transformations, an original categorical framework to deal with deterministic graph transformation with a maximal application strategy. Global transformations are based on the notion of mutual agreement (as opposed to mutual exclusion) which allows overlapping matchings to agree on the transformation of the shared part. Analogously to amalgamation of productions, mutual agreement is realized by considering additional rules specifying the behavior of the intersection parts. Global transformations are useful for expressing the global rewriting of a graph where no interface is explicitly conserved between the l.h.s. and the r.h.s. Taking a point of view di erent from substitution processes, a global transformation is a way to construct a set of constraints: local transformation constraints imply that for each l.h.s. matching the corresponding r.h.s. has to appear in the result; inclusion constraints state how r.h.s. have to be glued from l.h.s. inclusions. The resulting graph corresponds to the solution of these constraints.
In this paper, the formalization of global transformations relies on the cell
complexes category. We made this choice for bridging with other related works.
Firstly, our running example about mesh re nement is de nitively more clear
without any encoding in usual graphs. Secondly, this approach is in line with
the MGS programming language based on the rewriting of topological
collections [20]. In this context, labeled cell complexes are reminiscent of the MGS
topological collections and global transformations correspond to a new rule
application strategy. We plan to integrate this strategy in the current
implementation of the language. Finally, causal graphs dynamics proposed in [
From a pure algebraic point of view, the use of cell complexes is a detail. For
example, the global transformation framework can be moved seamlessly from
cell complexes to graphs. One can then ask what kind of general theory supports
global transformations in the same way that the essential properties of graphs
regarding DPOs have been identi ed leading to several axiomatic frameworks
(e.g., adhesive [
This research is partially supported by the French ANR grants \SynBioTIC" ANR-10-BLAN-0307 and \TARMAC" ANR-12-BS02-0007, and by the University Paris-Est Creteil. 15. Paun, G.: Computing with membranes. Journal of Computer and System Sciences 1(61), 108{143 (2000) 16. Prusinkiewicz, P., Lindenmayer, A., Hanan, J.S., et al.: The Algorithmic Beauty of Plants. Springer-Verlag (1990) 17. Raoult, J.C., Voisin, F.: Set-theoretic graph rewriting. Tech. Rep. RR-1665, INRIA (April 1992) 18. Rozenberg, G., Ehrig, H.: Handbook of graph grammars and computing by graph transformation, vol. 1. World scienti c Singapore (1999) 19. Rozenberg, G., Salomaa, A.: Lindenmayer Systems. Springer, Berlin (1992) 20. Spicher, A., Michel, O., Giavitto, J.L.: Declarative mesh subdivision using topological rewriting in MGS. In: ICGT 2010. LNCS, vol. 6372, pp. 298{313 (2010)