Graph rewriting

Terminology

• Normal form
• Confluent
• Terminating

Terminating and confluent system

When a GRS is terminating and confluent, we have the equivalence of the 4 strategies:

  Onf (S) ≃ Iter(S) ≃ Pick (Iter (S)) ≃ Iter (Pick (S))

They all compute one graph which is the unique normal form. In this case, the strategy Onf should be used because it is the more efficient one.

Terminating system

When a GRS is terminating, we have the equivalence of the two strategies:

  Onf (S) ≃ Pick (Iter (S))

See below for an example of non-terminating system where the equivalence does not hold.

Example of non-terminating rewriting system

The following code described a non-terminating rewriting system:

package S {
  rule B2A { pattern { e: N -[B]-> M } commands { del_edge e; add_edge N -[A]-> M } }
  rule B2C { pattern { e: N -[B]-> M } commands { del_edge e; add_edge N -[C]-> M } }
  rule C2B { pattern { e: N -[C]-> M } commands { del_edge e; add_edge N -[B]-> M } }
  rule C2D { pattern { e: N -[C]-> M } commands { del_edge e; add_edge N -[D]-> M } }
}

Each rule replaces an edge label by another. For instance, the rule B2A removes and edge with an B label and adds one with an A label.

Let G_A, G_B, G_C and G_D the 4 graphs with 2 nodes and 1 edge labelled A, B, C and D respectively.

The schema below shows how the 4 rules act on these 4 graphs:

Applying S to G_B

• The strategy Iter (S) applied to G_B produces the 2 graphs G_A and G_D.
• The strategy Pick (Iter (S)) applied to G_B may produce (unpredictably):
  • the graph G_A
  • the graph G_D
• The strategy Iter (Pick (S)) applied to G_B may produce (unpredictably):
  • the graph G_A
  • the graph G_D
  • the empty set
• The strategy Onf (S) applied to G_B may lead to (unpredictably):
  • the output of the graph G_A
  • the output of the graph G_D
  • a non-terminating execution

Note that all unpredictable behavior will be identical from one execution to another with the same input data. But, if the order of rules in the pacakge S is changed, the behavior may be different.