Term Graph Rewriting

From The Programming Languages and Systems Research Group
Jump to: navigation, search

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.

Term Graph Rewriting Literature


  • 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.

Further Information