TERM GRAPH REWRITING
Detlef Plump · WORLD SCIENTIFIC eBooks · 1999
Reduction Systems . . . . . . . . . . 5 1.3 Term Graphs . . . . . . . . . . . . . . . . . . . . 9 1.4 Term Graph Rewriting . . . . . . . . . . . . . . 15 1.5 Completeness . . . . . . . . . . . . . . . . . . . 23 1.6 Termination . . . . . . . . . . . . . . . . . . . . 29 1.7 Confluence . . . . . . . . . . . . . . . . . . . . . 37 1.8 Term Graph Narrowing . . . . . . . . . . . . . 45 1.9 Further Topics . . . . . . . . . . . . . . . . . . . 53 References . . . . . . . . . . . . . . . . . . . . . . . . . 54 3 4 CHAPTER 1. TERM GRAPH REWRITING 1.1 Introduction Term graph rewriting is concerned with the representation of functional expressions as graphs, and the evaluation of these expressions by rule-based graph transformation. Representing expressions as graphs is motivated by efficiency considerations. Consider, for example, the following rewrite rules for defining multiplication of natural numbers (where s denotes the successor function on natural numbers): x \\Theta 0 ! 0 x ...