Geometry of interaction for mall via Hughes-van Glabbeek proof-nets

研究成果: Article同行評審

2 引文 斯高帕斯(Scopus)

摘要

This article presents, for the first time, a Geometry of Interaction (GoI) interpretation inspired from Hughes-Van Glabbeek (HvG) proof-nets for multiplicative additive linear logic (MALL). Our GoI dynamically captures HvG's geometric correctness criterion-the toggling cycle condition-in terms of algebraic operators. Our new ingredient is a scalar extension of the ∗-algebra in Girard's ∗-ring of partial isometries over a Boolean polynomial ring with literals of eigenweights as indeterminates. To capture feedback arising from cuts, we construct a finer-grained execution formula. The expansion of this execution formula is longer than that for collections of slices for multiplicative GoI, hence it is harder to prove termination. Our GoI gives a dynamical, semantical account of Boolean valuations (in particular, pruning sub-proofs), conversion of weights (in particular, α-conversion), and additive (co)contraction, peculiar to additive proof-theory. Termination of our execution formula is shown to correspond to HvG's toggling criterion. The slice-wise restriction of our execution formula (by collapsing the Boolean structure) yields the well-known correspondence, explicit or implicit in previous works on multiplicative GoI, between the convergence of execution formulas and acyclicity of proof-nets. Feedback arising from the execution formula by restricting to the Boolean polynomial structure yields autonomous definability of eigenweights among cuts from the rest of the eigenweights.

原文English
文章編號25
期刊ACM Transactions on Computational Logic
19
發行號4
DOIs
出版狀態Published - 2018 11月

All Science Journal Classification (ASJC) codes

  • 理論電腦科學
  • 一般電腦科學
  • 邏輯
  • 計算數學

指紋

深入研究「Geometry of interaction for mall via Hughes-van Glabbeek proof-nets」主題。共同形成了獨特的指紋。

引用此