Title :
The Geometry of Interaction of Differential Interaction Nets
Author :
de Falco, Massimo
Author_Institution :
Inst. de Math. de Luminy, Univ. d´Aix-Marseil, Luminy
Abstract :
The geometry of interaction purpose is to give a semantic of proofs or programs accounting for their dynamics. The initial presentation, translated as an algebraic weighting of paths in proofnets, led to a better characterization of the lambda-lambda-calculus optimal reduction. Recently Ehrhard and Regnier have introduced an extension of the multiplicative exponential fragment of linear logic (MELL) that is able to express non-deterministic behaviour of programs and a proofnet-like calculus: differential interaction nets. This paper constructs a proper geometry of interaction (GoI) for this extension. We consider it both as an algebraic theory and as a concrete reversible computation. We draw links between this GoI and the one of MELL. As a by-product we give for the first time an equational theory suitable for the GoI of the multiplicative additive fragment of linear logic.
Keywords :
calculus; computational geometry; algebraic theory; concrete reversible computation; differential interaction nets; interaction purpose geometry; lambda-calculus optimal reduction; multiplicative additive fragment; multiplicative exponential fragment of linear logic; nondeterministic behaviour; Calculus; Computational geometry; Computer science; Concrete; Costs; Data mining; Electronic mail; Encoding; Equations; Logic programming; differential interaction nets; differential linear logic; geometry of interaction; linear logic; sharing graphs;
Conference_Titel :
Logic in Computer Science, 2008. LICS '08. 23rd Annual IEEE Symposium on
Conference_Location :
Pittsburgh, PA
Print_ISBN :
978-0-7695-3183-0
DOI :
10.1109/LICS.2008.23