MODULAR ASPECTS OF TERM GRAPH REWRITING

Term rewriting is generally implemented using graph rewriting for effi ciency reasons. Graph rewriting allows sharing of common structures th ereby saving both time and space. This implementation is sound in the sense that computation of a normal form of a graph yields a normal for m of the corresponding term. In this paper, we study modularity of the following properties in graph rewriting: (a) weak normalization, (b) strong normalization, (c) semi-completeness (confluence + weak normali zation) and (d) completeness (confluence + strong normalization). (C) 1998-Elsevier Science B.V. All rights reserved.