The theory of term graph rewriting allows to reason about computations on expressions with shared subexpressions. Sharing improves the efficiency of computations in space and time, and is ubiquitous in implementations of functional and logic programming languages, systems for automated deduction, and computer algebra systems.
Term graph rewriting provides a model to reason about the correctness, completeness and efficiency of term rewriting with shared subexpressions. This model reflects the properties of real implementations more adequately than the conventional, tree-based model of term rewriting. Sharing makes term graph rewriting different from term rewriting with respect to both efficiency and properties such as termination and confluence, thus requiring a theory different from established term rewriting theory.
D. Plump: Term Graph Rewriting. In Handbook of Graph Grammars and Computing by Graph Transformation, volume 2: Applications, Languages and Tools, chapter 1, pages 3-61, eds. H. Ehrig, G. Engels, H.-J. Kreowski and G. Rozenberg. World Scientific, 1999
TERMGRAPH 2009 - Fifth International Workshop on Computing with Terms and Graphs, York (United Kingdom), March 22, 2009
See the TERMGRAPH home page