Term Graph Rewriting
The theory of term graph rewriting allows one 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.
Contact Detlef Plump for more information.
Contents
Term Graph Rewriting Literature
Survey
- Detlef Plump. Term Graph Rewriting (.pdf). 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.
Refereed Journal, Conference, and Workshop Papers
- Detlef Plump. Essentials of Term Graph Rewriting (.pdf). In Proc. GETGRATS Closing Workshop, volume 51 of Electronic Notes in Theoretical Computer Science. Elsevier Science Publishers, 2002.
- Zena M. Ariola, Jan Willem Klop, and Detlef Plump. Bisimilarity in Term Graph Rewriting (.pdf). Information and Computation, 156(1/2):2-24, 2000.
Further Information
- Term Graph Rewriting - Detlef Plump's page on term graph rewriting.
