A confluent reduction for the λ-calculus with surjective pairing and terminal object
Journal of Functional Programming · 1996-03 · 6 (2) · 299-327
DOI: 10.1017/s0956796800001696 ↗Kurz gefasst
Fachartikel in der Zeitschrift Journal of Functional Programming, online erschienen am 07.11.2008. Verfasst von Pierre-Louis Curien und 1 weiteren Autor:innen. Die Arbeit wurde bisher 9-mal zitiert (Crossref) und nennt 25 Literaturangaben.
Abstract (Originalsprache)
We exhibit confluent and effectively weakly normalizing (thus decidable) rewriting systems for the full equational theory underlying cartesian closed categories, and for polymorphic extensions of it. The λ-calculus extended with surjective pairing has been well-studied in the last two decades. It is not confluent in the untyped case, and confluent in the typed case. But to the best of our knowledge the present work is the first treatment of the lambda calculus extended with surjective pairing and terminal object via a confluent rewriting system, and is the first solution to the decidability problem of the full equational theory of Cartesian Closed Categories extended with polymorphic types . Our approach yields conservativity results as well. In separate papers we apply our results to the study of provable type isomorphisms, and to the decidability of equality in a typed λ-calculus with subtyping.
Zitieren
APA
Curien, P., & Cosmo, R. D. (1996). A confluent reduction for the λ-calculus with surjective pairing and terminal object. Journal of Functional Programming, 6(2), 299-327. https://doi.org/10.1017/s0956796800001696
Vancouver
Curien P, Cosmo RD. A confluent reduction for the λ-calculus with surjective pairing and terminal object. Journal of Functional Programming. 1996;6(2):299-327. doi:10.1017/s0956796800001696
BibTeX
@article{Curien1996,
author = {Curien, Pierre-Louis and Cosmo, Roberto Di},
title = {A confluent reduction for the λ-calculus with surjective pairing and terminal object},
journal = {Journal of Functional Programming},
year = {1996},
volume = {6},
number = {2},
pages = {299--327},
doi = {10.1017/s0956796800001696}
}
EUVIMED