Formal SOS-Proofs for the Lambda-Calculus - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Communication Dans Un Congrès Année : 2009

Formal SOS-Proofs for the Lambda-Calculus

Résumé

We describe in this paper formalisations for the properties of weakening, type-substitutivity, subject-reduction and termina- tion of the usual big-step evaluation relation. Our language is the lambda-calculus whose simplicity allows us to show actual theorem-prover code of the formal proofs. The formalisations are done in Nominal Isabelle, a de?nitional extention of the theorem prover Isabelle/HOL. The point of these formalisations is to be as close as possible to the ?pencil-and-paper? proofs for these properties, but of course be completely rigorous. We describe where Nominal Isabelle is of great help with such formalisations and where one has to invest additional effort in order to obtain formal proofs.
Fichier principal
Vignette du fichier
SOS-lsfa08.pdf (181.98 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

inria-00335718 , version 1 (30-10-2008)

Identifiants

Citer

Christian Urban, Julien Narboux. Formal SOS-Proofs for the Lambda-Calculus. Third Workshop on Logical and Semantic Frameworks, with Applications, Mauricio Ayala-Rincón, Aug 2008, Salvador, Brazil. pp.139-155, ⟨10.1016/j.entcs.2009.07.053⟩. ⟨inria-00335718⟩

Collections

CNRS SITE-ALSACE
84 Consultations
178 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More