Continuation-passing Style Models Complete for Intuitionistic Logic - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Article Dans Une Revue Annals of Pure and Applied Logic Année : 2012

Continuation-passing Style Models Complete for Intuitionistic Logic

Résumé

A class of models is presented, in the form of continuation monads polymorphic for first-order individuals, that is sound and complete for minimal intuitionistic predicate logic. The proofs of soundness and completeness are constructive and the computational content of their composition is, in particular, a $\beta$-normalisation-by-evaluation program for simply typed lambda calculus with sum types. Although the inspiration comes from Danvy's type-directed partial evaluator for the same lambda calculus, the there essential use of delimited control operators (i.e. computational effects) is avoided. The role of polymorphism is crucial -- dropping it allows one to obtain a notion of model complete for classical predicate logic. The connection between ours and Kripke models is made through a strengthening of the Double-negation Shift schema.
Fichier principal
Vignette du fichier
intcomp.pdf (227.48 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

hal-00647390 , version 1 (02-12-2011)
hal-00647390 , version 2 (03-12-2011)
hal-00647390 , version 3 (09-05-2012)

Identifiants

Citer

Danko Ilik. Continuation-passing Style Models Complete for Intuitionistic Logic. Annals of Pure and Applied Logic, 2012, ⟨10.1016/j.apal.2012.05.003⟩. ⟨hal-00647390v3⟩
387 Consultations
455 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More