EUVIMEDEUVIMED entdecken
Crossref

A confluent reduction for the λ-calculus with surjective pairing and terminal object

Pierre-Louis Curien, Roberto Di Cosmo

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.

AbstractBibliografische AngabenZitierenVerwandte Studien

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}
}
Kostenlos starten →