Skip to Main content Skip to Navigation
Conference papers

Infinitary Lambda Calculi from a Linear Perspective

Ugo Dal Lago 1, 2
2 FOCUS - Foundations of Component-based Ubiquitous Systems
CRISAM - Inria Sophia Antipolis - Méditerranée , DISI - Dipartimento di Informatica - Scienza e Ingegneria [Bologna]
Abstract : We introduce a linear infinitary λ-calculus, called Λ∞, in which two exponential modalities are available, the first one being the usual, finitary one, the other being the only construct interpreted coinductively. The obtained calculus embeds the infinitary applica-tive λ-calculus and is universal for computations over infinite strings. What is particularly interesting about Λ∞, is that the refinement induced by linear logic allows to restrict both modalities so as to get calculi which are terminating inductively and productive coin-ductively. We exemplify this idea by analysing a fragment of Λ built around the principles of SLL and 4LL. Interestingly, it enjoys confluence, contrarily to what happens in ordinary infinitary λ-calculi.
Document type :
Conference papers
Complete list of metadata

Cited literature [30 references]  Display  Hide  Download
Contributor : Ugo Dal Lago Connect in order to contact the contributor
Submitted on : Tuesday, November 22, 2016 - 4:02:44 PM
Last modification on : Friday, October 30, 2020 - 12:04:03 PM
Long-term archiving on: : Monday, March 27, 2017 - 9:19:44 AM


main (1).pdf
Files produced by the author(s)




Ugo Dal Lago. Infinitary Lambda Calculi from a Linear Perspective. Logic in Computer Science, Jul 2016, New York, United States. ⟨10.1145/2933575.2934505⟩. ⟨hal-01400883⟩



Les métriques sont temporairement indisponibles