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 :
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:
- cl, dl : L -> Nat are total functions which assign each label a unique creation (cl) and a unique deletion (dl) layersuch 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.
- 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).