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.