HAL will be down for maintenance from Friday, June 10 at 4pm through Monday, June 13 at 9am. More information
Skip to Main content Skip to Navigation

$\lambda\upsilon$, a calculus of explicit substitutions which preserves strong normalisation

Abstract : Explicit substitutions were proposed by Abadi, Cardelli, Curien, Hardin and Lévy to internalise substitutions into $\lambda$-calculus and to propose a mechanism for computing on substitutions. $\lambda\upsilon$ is another view of the same concept which aims to explain the process of substitution and to decompose it in small steps. $\lambda\upsilon$ is simple and preserves strong normalisation. Apparently that important property cannot stay with another important one, namely confluence on open terms. The spirit of $\lambda\upsilon$ is closely related to another calculus of explicit substitutions proposed by de Bruijn and called $C\lambda\xi\phi$. In this paper, we introduce $\lambda\upsilon$, we present $C\lambda\xi\phi$ in the same framework as $\lambda\upsilon$ and we compare both calculi. Moreover, we prove properties of $\lambda\upsilon$; namely $\lambda\upsilon$ correctly implements $\beta$ reduction, $\lambda\upsilon$ is confluent on closed terms, i.e., on terms of classical $\lambda$-calculus and on all terms that are derived from those terms, and finally $\lambda\upsilon$ preserves strong normalization of $\beta$-reduction.
Document type :
Complete list of metadata

Contributor : Rapport de Recherche Inria Connect in order to contact the contributor
Submitted on : Wednesday, May 24, 2006 - 2:43:58 PM
Last modification on : Friday, February 4, 2022 - 3:21:33 AM
Long-term archiving on: : Sunday, April 4, 2010 - 10:13:23 PM


  • HAL Id : inria-00074197, version 1



Zine-El-Abidine Benaissa, Daniel Briaud, Pierre Lescanne, Jocelyne Rouyer-Degli. $\lambda\upsilon$, a calculus of explicit substitutions which preserves strong normalisation. [Research Report] RR-2477, INRIA. 1995. ⟨inria-00074197⟩



Record views


Files downloads