A semantic measure of the execution time in Linear Logic - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Rapport (Rapport De Recherche) Année : 2008

A semantic measure of the execution time in Linear Logic

Résumé

We give a semantic account of the execution time (i.e. the number of cut-elimination steps leading to the normal form) of an untyped MELL (proof-)net. We first prove that: 1) a net is head-normalizable (i.e. normalizable at depth 0) if and only if its interpretation in the multiset based relational semantics is not empty and 2) a net is normalizable if and only if its exhaustive interpretation (a suitable restriction of its interpretation) is not empty. We then define a size on every experiment of a net, and we precisely relate the number of cut-elimination steps of every stratified reduction sequence to the size of a particular experiment. Finally, we give a semantic measure of execution time: we prove that we can compute the number of cut-elimination steps leading to a cut free normal form of the net obtained by connecting two cut free nets by means of a cut link, from the interpretations of the two cut free nets. These results are inspired by similar ones obtained by the first author for the (untyped) lambda-calculus.
Fichier principal
Vignette du fichier
normbysem_Rel.pdf (584.7 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)

Dates et versions

inria-00206099 , version 1 (16-01-2008)
inria-00206099 , version 2 (29-01-2008)
inria-00206099 , version 3 (01-02-2008)
inria-00206099 , version 4 (04-02-2008)

Identifiants

  • HAL Id : inria-00206099 , version 3

Citer

Daniel de Carvalho, Michele Pagani, Lorenzo Tortora de Falco. A semantic measure of the execution time in Linear Logic. [Research Report] 2008, pp.48. ⟨inria-00206099v3⟩

Collections

PPS
191 Consultations
312 Téléchargements

Partager

Gmail Facebook X LinkedIn More