Term Graph Rewriting

Detlef Plump
Universität Bremen

Term graph rewriting is concerned with the representation of expressions as graphs, and the evaluation of these expressions by rule-based graph transformation. Representing expressions as graphs allows to share common subexpressions, improving the efficiency of term rewriting in space and time. Term graph rewriting reflects the properties of real implementations of term rewriting based on shared structures, and has applications in functional and logic programming and in automated reasoning. Besides efficiency, term graph rewriting differs from conventional term rewriting in properties like termination and confluence. I will give a survey of term graph rewriting, emphasizing the relations between term rewriting and term graph rewriting. I will focus on soundness and completeness of term graph rewriting, and on termination and confluence. Moreover, I will address term graph narrowing which allows to solve equations and provides an operational principle for combining functional and logic programming.

Back to seminar homepage