Explicit substitution on the edge of strong normalisation

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 ß-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: ¿¿ of Lescanne et al., ¿s of Kamareddine and Rios and ¿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 Melliès 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 ¿x the set of terms of the explicit substitution calculus, we look at the set ¿xrpo on labelled terms, such that any infinite ¿x-reduction path starting from an A e ¿xrpo-descending sequence. The well-founded order >rpo is defined by using a technique similar to semantic labelling.