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 条
  • [11] A lambda-calculus for dynamic binding
    Dami, L
    THEORETICAL COMPUTER SCIENCE, 1998, 192 (02) : 201 - 231
  • [12] EXTENDING THE LAMBDA-CALCULUS WITH UNBIND AND REBIND
    Dezani-Ciancaglini, Mariangiola
    Giannini, Paola
    Zucca, Elena
    RAIRO-THEORETICAL INFORMATICS AND APPLICATIONS, 2011, 45 (01): : 143 - 162
  • [13] Backpropagation in the Simply Typed Lambda-Calculus with Linear Negation
    Brunel, Alois
    Mazza, Damiano
    Pagani, Michele
    PROCEEDINGS OF THE ACM ON PROGRAMMING LANGUAGES-PACMPL, 2020, 4 (POPL):
  • [14] The Bang Calculus: an untyped lambda-calculus generalizing Call-By-Name and Call-By-Value
    Ehrhard, Thomas
    Guerrieri, Giulio
    PROCEEDINGS OF THE 18TH INTERNATIONAL SYMPOSIUM ON PRINCIPLES AND PRACTICE OF DECLARATIVE PROGRAMMING (PPDP 2016), 2016, : 174 - 187
  • [15] SEMANTICS OF TYPED LAMBDA-CALCULUS WITH CONSTRUCTORS
    Petit, Barbara
    LOGICAL METHODS IN COMPUTER SCIENCE, 2011, 7 (01)
  • [16] ON CONSTRUCTOR REWRITE SYSTEMS AND THE LAMBDA-CALCULUS
    Dal Lago, Ugo
    Martini, Simone
    LOGICAL METHODS IN COMPUTER SCIENCE, 2012, 8 (03)
  • [17] Parallel Reduction in Resource Lambda-Calculus
    Pagani, Michele
    Tranquilli, Paolo
    PROGRAMMING LANGUAGES AND SYSTEMS, PROCEEDINGS, 2009, 5904 : 226 - +
  • [18] TILC: The Interactive Lambda-Calculus Tracer
    Ruiz, David
    Villaret, Mateu
    ELECTRONIC NOTES IN THEORETICAL COMPUTER SCIENCE, 2009, 248 : 173 - 183
  • [19] THE BASIS DECISION PROBLEM IN LAMBDA-CALCULUS
    INTRIGILA, B
    MATHEMATICAL LOGIC QUARTERLY, 1993, 39 (02) : 178 - 180
  • [20] Lambda-calculus, combinators and applicative computational technologies
    Ismailova, Larisa
    Wolfengagen, Viacheslav
    Kosikov, Sergey
    COGNITIVE SYSTEMS RESEARCH, 2022, 76 : 93 - 100