Computing with Graphs and Graph Rewriting

Dorothea Blostein, Andy Schürr

           Graphs are a popular data structure. Programmers are faced with
           the need represent, inspect, modify, display and recognize
           graphs. In this paper we describe a systematic approach to
           graph modification, using graph rewrite rules. Graph rewrite
           rules replace one subgraph by another subgraph. In other words,
           a graph rewrite rule specifies how, and under what conditions,
           to replace one piece of a graph by another piece. This is an
           intuitive and useful generalization of string rewriting. We
           illustrate these ideas using a sampling of applications:
           precedence-network creation, visual language editing,
           and recognition of mathematics notation.  Graph rewriting
           examples are written in PROGRES, a programming language with
           both visual and textual elements.