Explicit substitution - On the edge of strong normalization
We use the recursive path ordering (RPO) technique of semantic labelling to show the preservation of strong normalization (PSN) property for several calculi of explicit substitution. PSN states that if a term M is strongly normalizing under ordinary beta-reduction (using 'global' substitutions), then it is strongly normalizing if the substitution is made explicit ('local'). There are different ways of making global substitution explicit and PSN is a quite natural and desirable property for the explicit substitution calculus. Our method for proving PSN is very general and applies to several known systems of explicit substitutions, both with named variables and with De Bruijn indices: lambda v of Lescanne et al., lambda s of Kamareddine and Rios and lambda x of Rose and Bloo. We also look at two small extensions of the explicit substitution calculus that allow to permute substitutions. For one of these extensions PSN fails (using the counterexample in Mellies 1995). For the other we can prove PSN using our method, thus showing the subtlety of the subject and the generality of our method. One of the key ideas behind our proof is that, for lambda x the set of terms of the explicit substitution calculus, we look at the set lambda x( (rpo) on labelled terms, such that any infinite lambda x-reduction path starting from an A is an element of lambda x( (rpo)-descending sequence. The well-founded order >(rpo) is defined by using a technique similar to semantic labelling. (C) 1999-Elsevier Science B.V. All rights reserved.
explicit substitution recursive path order lambda-calculus