The adequacy of term graph rewriting for simulating term rewriting
Richard Kennaway, Jan Willem Klop, M. Ronan Sleep, Fer-Jan J. de Vries · Centrum Wiskunde & Informatica (CWI), the national research institute for mathematics and computer science in the Netherlands · 1993
What does it mean to say that a Graph Rewrite System (GRAPHS, -+graph) is an implementation of a Term Rewrite System (TERMS, -+term)?The intuitive answer is (cf.[vEB90]): everything which term rewriting can do can be performed by graph rewriting as well, modulo the unravelling of graphs to terms.Unfortunately, if we insist on this notion, we soon discover that graph rewriting does not implement term rewriting.For example, consider rules such as D( x) --+ P(x, x), A--+ B, P(A, B)--+ C. With term rewriting we get the sequence: D(A) -+term P(A, A) -+term P(A, B) -+term C, so that D(A)-+* C using term rewriting.But with graph rewriting, the rule D(x) -+graph P(x, x) copies only a pointer to the subterm x, and the only possible graph rewriting of D(A) is the sequence D(A) -+graph P(A, A) -+graph P (B, B).So, unlike term rewriting, graph rewriting cannot rewrite D(A) to C. With term rewriting, two distinct copies of the argument x of the rule D( x) --+ P(x, x) are made, and can be treated differently in subsequent term rewriting.With graph rewriting, such duplicating rules copy only pointers, and any subsequent rewrites of the subterm referenced by such a pointer is experienced by every term graph using that pointer.This is good for operational efficiency, but bad if we want to preserve term rewriting•semantics.The main purpose of this chapter is to identify precisely a class of term rewriting systems whose semantics are preserved by graph rewriting implementations.