Layered graph transformation in   

 

 

Layered graph grammar

Rule   layers

The layers fix the order how rules are applied. The interpretation process first has to apply rules of layer 0 as long as possible, then rules of layer 1, etc. Using rule layers makes it possible to specify a  simple control flow  of graph transformation.

Layering   conditions

Using rule layers together with deletion/creation type layers allows some kind of optimization during critical pairs analysis in the way that critical pairs are searched for rules in the same layer only, parsing when the parsing process might not terminate : First all rules of one layer are applied as long as possible before the rules of the next layer are applied.

We define so-called  layering conditions.  Rule and type layers are introduced such that each rule deletes at least one graph object which is of the same or a lower layer, creates graph objects of a greater layer only, has negative application conditions with graph objects of the current or lower layers only.

Layering   functions

Given the set L of all node and edge labels and the set R of all rules we introduce the following  layering functions : cl, dl : L -> Nat are total functions which assign each label a unique creation (cl) and a unique deletion (dl) layer  such that forall   l   in L:   0  < =  cl (l)  < =  dl (l)  < =  n. rl : R -> Nat is a total function which assigns each rule a unique layer. A graph transformation system with a set  R  of rules over a set  L  of node and edge labels with layering functions  as above is a  layered graph transformation system  if and only if all rules  r in R  with  rl (r) = k  fulfill the following constraints:  r  deletes at least one node or edge.  r deletes only nodes and edges with labels  l  such that  dl (l) <= k .  r  creates only nodes and edges with labels  l  such that  cl (l) > k .  r  uses only NACs over nodes and edges with labels  l  such that  cl (l) <= k .

 

Graphical user interface

We provide following the  Layer  options  in  Preferences/Options... Figure 1 shows the possible settings: Figure 1. Layer options   < Rule, Creation, Deletion, Rule must delete, NAC check >   satisfies conditions (1), (2), (3) and (4).   < Rule, Creation, Deletion, NAC check >   satisfies conditions (2), (3) and  (4).   < Rule, Creation, Deletion, Rule must delete >   satisfies conditions (1), (2) and (3).   < Rule, Creation, Deletion >   satisfies conditions (2) and (3). The layer function is checked if  option Layered is selected in options of   Critical Pair Analysis   or   Parser .

 

Revision: