KIT | KIT-Bibliothek | Impressum | Datenschutz

On computational interpretations of the modal logic S4. IIIa. Termination, confluence, conservativity of lambda-evQ

Goubault-Larrecq, Jean

Abstract:


A language of constructions for minimal logic is the
λ-calculus, where cut-elimination is encoded as
β-reduction. We examine corresponding languages for the
minimal version of the modal logic S4, with notions of reduction
that encodes cut-elimination for the corresponding sequent system.
It turns out that a natural interpretation of the latter
constructions is a λ-calculus extended by an idealized
version of Lisp's \verb/eval/ and \verb/quote/ constructs.

In this Part IIIa, we examine the termination and confluence
properties of the λ\tt ev\/Q and negative:
the typed calculi do not terminate, the subsystems Σ and
ΣH that propagate substitutions, quotations andevaluations
downwards do not terminate either in the untyped case, and the
untyped λ\tt ev\/QH-calculus is not confluent.
However, the typed versions of Σ and ΣH do terminate,
so the typed λ\tt ev\/Q-calculus is confluent.
It follows that the typed λ\tt ev\/Q-calculus is a
conservative extension of the typed λS4-calculus.

Part IIIb will cover the confluence of the typed
... mehr

Zugehörige Institution(en) am KIT Fakultät für Informatik – Institut für Logik, Komplexität und Deduktionssysteme (ILKD)
Publikationstyp Buch
Publikationsjahr 1996
Sprache Englisch
Identifikator urn:nbn:de:swb:90-AAA402965
KITopen-ID: 40296
Erscheinungsvermerk Karlsruhe 1996. (Interner Bericht. Fakultät für Informatik, Universität Karlsruhe. 1996,33.)

Volltext §
DOI: 10.5445/IR/40296
Seitenaufrufe: 70
seit 01.08.2019
Downloads: 294
seit 08.01.2009
Cover der Publikation
KIT – Die Forschungsuniversität in der Helmholtz-Gemeinschaft
KITopen Landing Page