More on Graph Rewriting With Contextual Refinement

Abstract

In GRGEN , a graph rewrite generator tool, rules have the outstanding
feature that variables in their pattern and replacement graphs may be refined with
meta-rules based on contextual hyperedge replacement grammars. A refined rule may
delete, copy, and transform subgraphs of unbounded size and of variable shape. In
this paper, we show that rules with contextual refinement can be transformed to stan-
dard graph rewrite rules that perform the refinement incrementally, and are applied
according to a strategy called residual rewriting. With this transformation, it is possi-
ble to state precisely whether refinements can be determined in finitely many steps or
not, and whether refinements are unique for every form of refined pattern or not.