Intuitionistic differential nets and lambda-calculus

被引:15
作者
Tranquilli, Paolo [1 ]
机构
[1] Univ Lyon 1, INRIA Ecole Normale Super Lyon, CNRS, Lab Informat Parallelisme,UMR 5668, F-69622 Villeurbanne, France
关键词
Lambda-calculus; Differential interaction nets; Linear logic; Proof nets; Exponential reduction; Confluence; Normalization; MU-CALCULUS; TERMS;
D O I
10.1016/j.tcs.2010.12.022
中图分类号
TP301 [理论、方法];
学科分类号
081202 ;
摘要
We define pure intuitionistic differential proof nets, extending Ehrhard and Regnier's differential interaction nets with the exponential box of Linear Logic. Normalization of the exponential reduction and confluence of the full one is proved. These results are directed and adjusted to give a translation of Boudol's untyped lambda-calculus with resources extended with a linear-nonlinear reduction a la Ehrhard and Regnier's differential lambda-calculus. Such reduction comes in two flavours: baby-step and giant-step beta-reduction. The translation, based on Girard's encoding A -> B similar to !A (sic) B and as such extending the usual one for lambda-calculus into proof nets, enjoys bisimulation for giant-step beta-reduction. From this result we also derive confluence of both reductions. (C) 2010 Elsevier B.V. All rights reserved.
引用
收藏
页码:1979 / 1997
页数:19
相关论文
共 50 条