Lifting infinite normal form definitions from term rewriting to term graph rewriting

Infinite normal forms are a way of giving semantics to non-terminating rewrite systems. The notion is a generalization of the Boehm tree in the lambda calculus. It was first introduced in [AB97] to provide semantics for a lambda calculus on terms with letrec. In that paper infinite normal forms were defined directly on the graph rewrit e system. In [Blo01] the framework was improved by defining the infinite normal form of a term graph using the infinite normal form on terms. This approach of lifting the definition makes the non-confluence problems introduced into term graph rewriting by substitution rules much easier to deal with. In this paper, we give a simplified presentation of the latter approach.