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 applicative -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 coinductively. 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.
Infinitary Lambda Calculi from a Linear Perspective / Dal Lago, Ugo. - ELETTRONICO. - (2016), pp. 447-456. (Intervento presentato al convegno 31st Annual ACM/IEEE Symposium on Logic in Computer Science, LICS 2016 tenutosi a Columbia University, New York, USA nel 2016) [10.1145/2933575.2934505].
Infinitary Lambda Calculi from a Linear Perspective
DAL LAGO, UGO
2016
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 applicative -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 coinductively. 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.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
