Quantitative Types for the Linear Substitution Calculus

Abstract : We define two non-idempotent intersection type systems for the linear substitution calculus, a calculus with partial substitutions acting at a distance that is a computational interpretation of linear logic proof-nets. The calculus naturally express linear-head reduction, a notion of evaluation of proof nets that is strongly related to abstract machines. We show that our first (resp. second) quantitave type system characterizes linear-head, head and weak (resp. strong) normalizing sets of terms. All such characterizations are given by means of combinatorial arguments, i.e. there is a measure based on type derivations which decreases with respect to each reduction relation considered in the paper.
Type de document :
Communication dans un congrès
Josep Diaz; Ivan Lanese; Davide Sangiorgi. 8th IFIP International Conference on Theoretical Computer Science (TCS), Sep 2014, Rome, Italy. Springer, Lecture Notes in Computer Science, LNCS-8705, pp.296-310, 2014, Theoretical Computer Science. 〈10.1007/978-3-662-44602-7_23〉
Liste complète des métadonnées

Littérature citée [40 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-01402078
Contributeur : Hal Ifip <>
Soumis le : jeudi 24 novembre 2016 - 11:08:59
Dernière modification le : jeudi 11 janvier 2018 - 06:17:49
Document(s) archivé(s) le : mardi 21 mars 2017 - 04:36:29

Fichier

978-3-662-44602-7_23_Chapter.p...
Fichiers produits par l'(les) auteur(s)

Licence


Distributed under a Creative Commons Paternité 4.0 International License

Identifiants

Citation

Delia Kesner, Daniel Ventura. Quantitative Types for the Linear Substitution Calculus. Josep Diaz; Ivan Lanese; Davide Sangiorgi. 8th IFIP International Conference on Theoretical Computer Science (TCS), Sep 2014, Rome, Italy. Springer, Lecture Notes in Computer Science, LNCS-8705, pp.296-310, 2014, Theoretical Computer Science. 〈10.1007/978-3-662-44602-7_23〉. 〈hal-01402078〉

Partager

Métriques

Consultations de la notice

106

Téléchargements de fichiers

48