Practical Use of Graph Rewriting

Abstract

graphs (in which subgraphs are represented by a single node, and groups of edges are bundled into a single edge) are supported in the prototype algebraic-rewrite environment of [LöBe93]. This graph structuring is motivated by the need for convenient selection of subgraphs and morphisms for rule application, not by a desire to rewrite hierarchical host-graphs. Hierarchical graph structure can be described by allowing node-labels to be graphs themselves. In the algebraic rewriting formalism of [Schn93], labels can be complex categorical objects (including graphs), instead of being restricted to atomic objects drawn from an alphabet. These complex labels can be rewritten during rewrite-rule application (unlike the label-preserving graph morphisms of more restrictive algebraic rewrite systems). It would be interesting to gain practical experience in the use of this rewriting formalism. Hierarchical graph structure can be captured by a flat host-graph combined with a set of graph-rewriting ...