A Concurrent Model for Linear Logic

被引:14
作者
Beffara, Emmanuel [1 ,2 ]
机构
[1] Univ Paris 07, PPS, Paris, France
[2] CNRS, Paris, France
关键词
Linear logic; pi-calculus; proofs as processes;
D O I
10.1016/j.entcs.2005.11.055
中图分类号
TP301 [理论、方法];
学科分类号
081202 ;
摘要
We build a realizability model for linear logic using a name-passing process calculus. The construction is based on testing semantics for processes, drawing ideas from spatial and modal logics, and yields a new type system for process calculi that ensures termination while allowing significantly concurrent behaviours. Then we study how embeddings of intuitionistic and classical logics into linear logic induce typed translations of lambda and lambda mu calculi in which new concurrent instructions can be introduced, thus sketching the basis for a Curry-Howard interpretation of linear and classical proofs in terms of concurrent interaction.
引用
收藏
页码:147 / 168
页数:22
相关论文
共 22 条
[1]  
Abramsky, 1993, THEORY FORMAL METHOD, P57, DOI 10.1007/978-1-4471-3503-6_5
[2]   COMPUTATIONAL INTERPRETATIONS OF LINEAR LOGIC [J].
ABRAMSKY, S .
THEORETICAL COMPUTER SCIENCE, 1993, 111 (1-2) :3-57
[3]  
Abramsky Samson, 2001, ELECT NOTES THEORETI, V23
[4]   ON THE PI-CALCULUS AND LINEAR LOGIC [J].
BELLIN, G ;
SCOTT, PJ .
THEORETICAL COMPUTER SCIENCE, 1994, 135 (01) :11-65
[5]  
Berger M, 2003, LECT NOTES COMPUT SC, V2620, P103
[6]   TESTING EQUIVALENCE FOR MOBILE PROCESSES [J].
BOREALE, M ;
DENICOLA, R .
INFORMATION AND COMPUTATION, 1995, 120 (02) :279-303
[7]   A spatial logic for concurrency - II [J].
Caires, L ;
Cardelli, L .
THEORETICAL COMPUTER SCIENCE, 2004, 322 (03) :517-565
[8]  
Cleaveland Rance, 1990, INT WORKSH AUT VER M, P11
[9]   The duality of computation [J].
Curien, PL ;
Herbelin, H .
ACM SIGPLAN NOTICES, 2000, 35 (09) :233-243
[10]  
Dam M., 1994, Journal of Logic and Computation, V4, P939, DOI 10.1093/logcom/4.6.939