De Bruijn's syntax and reductional behaviour of lambda-terms: the untyped case
In this paper, a notation influenced by de Bruijn's syntax of the lambda-calculus is used to describe canonical forms of terms and an equivalence relation which divides terms into classes according to their reductional behaviour. We show that this notation helps describe canonical forms more elegantly than the classical notation. We define reduction modulo equivalence classes of terms up to the permutation of redexes in canonical forms and show that this reduction contains other notions of reductions in the literature including the sigma-reduction of Regnier. We establish all the desirable properties of our reduction modulo equivalence classes for the untyped lambda-calculus. (C) 2004 Elsevier Inc. All rights reserved.
reductional behaviour canonical forms class reduction