Strong Normalization from Weak Normalization in Typedλ-Calculi

AbstractFor some typedλ-calculi it is easier to prove weak normalization than strong normalization. Techniques to infer the latter from the former have been invented over the last twenty years by Nederpelt, Klop, Khasidashvili, Karr, de Groote, and Kfoury and Wells. However, these techniques infer strong normalization of one notion of reduction from weak normalization of amore complicatednotion of reduction. This paper presents a new technique to infer strong normalization of a notion of reduction in a typedλ-calculus from weak normalization of thesamenotion of reduction. The technique is demonstrated to work on some well-known systems including second-orderλ-calculus and the system of positive, recursive types. It gives hope for a positive answer to the Barendregt–Geuvers conjecture stating that every pure type system which is weakly normalizing is also strongly normalizing. The paper also analyzes the relationship between the techniques mentioned above, and reviews, in less detail, other techniques for proving strong normalization