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(<infinity), consisting of the terms A such that the substitution-normal-form of each subterm of A is beta-SN. This is a kind of 'induction loading': if we prove that lambda x-reduction is SN on the set lambda x(<infinity), then we have proved PSN for lambda x. To prove lambda x-SN on the set lambda x(<infinity), We define the beta-size of a term A is an element of lambda x(<infinity) as the maximum length of a beta-reduction path from the substitution-normal-form of A. Using this beta-size, we define a translation from lambda x(<infinity) to some well-founded order >(rpo) on labelled terms, such that any infinite lambda x-reduction path starting from an A is an element of lambda x(<infinity) translates to an infinite >(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.
