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 条
  • [1] The differential lambda-calculus
    Ehrhard, T
    Regnier, L
    THEORETICAL COMPUTER SCIENCE, 2003, 309 (1-3) : 1 - 41
  • [2] An Infinitary Affine Lambda-Calculus Isomorphic to the Full Lambda-Calculus
    Mazza, Damiano
    2012 27TH ANNUAL ACM/IEEE SYMPOSIUM ON LOGIC IN COMPUTER SCIENCE (LICS), 2012, : 471 - 480
  • [3] A linear linear lambda-calculus
    Diaz-Caro, Alejandro
    Dowek, Gilles
    MATHEMATICAL STRUCTURES IN COMPUTER SCIENCE, 2024, : 1103 - 1137
  • [4] Package Duplication in Interaction Nets and Weak Head Reduction in the lambda-calculus
    Institut de Mathématiques de Luminy, Marseille, France
    Electron. Notes Theor. Comput. Sci., 2007, 1 SPEC. ISS. (75-86): : 75 - 86
  • [5] Two-level Lambda-calculus
    Gabbay, Murdoch J.
    Mulligan, Dominic P.
    ELECTRONIC NOTES IN THEORETICAL COMPUTER SCIENCE, 2009, 246 : 107 - 129
  • [6] Focused Linear Logic and the lambda-calculus
    Brock-Nannestad, Taus
    Guenot, Nicolas
    ELECTRONIC NOTES IN THEORETICAL COMPUTER SCIENCE, 2015, 319 : 103 - 119
  • [7] Lambda-calculus with director strings
    Fernández, M
    Mackie, I
    Sinot, FR
    APPLICABLE ALGEBRA IN ENGINEERING COMMUNICATION AND COMPUTING, 2005, 15 (06) : 393 - 437
  • [8] Spinal Atomic Lambda-Calculus
    Sherratt, David
    Heijltjes, Willem
    Gundersen, Tom
    Parigot, Michel
    FOUNDATIONS OF SOFTWARE SCIENCE AND COMPUTATION STRUCTURES, FOSSACS 2020, 2020, 12077 : 582 - 601
  • [9] Solvability in Resource Lambda-Calculus
    Pagani, Michele
    della Rocca, Simona Ronchi
    FOUNDATIONS OF SOFTWARE SCIENCE AND COMPUTATIONAL STRUCTURES, PROCEEDINGS, 2010, 6014 : 358 - 373
  • [10] Development Separation in Lambda-Calculus
    Xi, Hongwei
    ELECTRONIC NOTES IN THEORETICAL COMPUTER SCIENCE, 2006, 143 : 207 - 221