Hostname: page-component-cd9895bd7-hc48f Total loading time: 0 Render date: 2024-12-22T20:20:47.039Z Has data issue: false hasContentIssue false
  • English
  • Français

A MALL geometry of interaction based on indexed linear logic

Published online by Cambridge University Press:  14 June 2021

Masahiro Hamano Open the ORCID record for Masahiro Hamano [Opens in a new window]
Masahiro Hamano*
Affiliation:
Miin Wu School of Computing, National Cheng Kung University, No1, University Road, Tainan City 70101, Taiwan
*
Email: [email protected]
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the ‘Save PDF’ action button.

We construct a geometry of interaction (GoI: dynamic modelling of Gentzen-style cut elimination) for multiplicative-additive linear logic (MALL) by employing Bucciarelli–Ehrhard indexed linear logic MALL(I) to handle the additives. Our construction is an extension to the additives of the Haghverdi–Scott categorical formulation (a multiplicative GoI situation in a traced monoidal category) for Girard’s original GoI 1. The indices are shown to serve not only in their original denotational level, but also at a finer grained dynamic level so that the peculiarities of additive cut elimination such as superposition, erasure of subproofs, and additive (co-) contraction can be handled with the explicit use of indices. Proofs are interpreted as indexed subsets in the category Rel, but without the explicit relational composition; instead, execution formulas are run pointwise on the interpretation at each index, with respect to symmetries of cuts, in a traced monoidal category with a reflexive object and a zero morphism. The sets of indices diminish overall when an execution formula is run, corresponding to the additive cut-elimination procedure (erasure), and allowing recovery of the relational composition. The main theorem is the invariance of the execution formulas along cut elimination so that the formulas converge to the denotations of (cut-free) proofs.

Keywords

Geometry of interactionMultiplicative Additive Linear LogicIndexed Linear LogicCut EliminationTraced Monoidal CategoryExecution Formula
Type
Paper
Information
Mathematical Structures in Computer Science , Volume 30 , Issue 10 , November 2020 , pp. 1025 - 1053
Check for updates
Creative Commons
Creative Common License - CCCreative Common License - BY
This is an Open Access article, distributed under the terms of the Creative Commons Attribution licence (http://creativecommons.org/licenses/by/4.0/), which permits unrestricted re-use, distribution, and reproduction in any medium, provided the original work is properly cited.
Copyright
© The Author(s), 2021. Published by Cambridge University Press

References

Bucciarelli, A. and Ehrhard, T. (2000). On phase semantics and denotational semantics in multiplicative-additive linear logic. Annals of Pure and Applied Logic 102 (3) 247–282.CrossRefGoogle Scholar
Bucciarelli, A. and Ehrhard, T. (2001). On phase semantics and denotational semantics: the exponentials. Annals of Pure and Applied Logic 109 (3) 205–241.CrossRefGoogle Scholar
Danos, V. and Regnier, L. (1995). Proof-nets and the Hilbert space. In: Girard, J.-Y., Lafont, Y. and Regnier, L. (eds.) Advances in Linear Logic, Cambridge University Press, UK, 307–328.CrossRefGoogle Scholar
Duchesne, E. (2009). La Localisation en Logique: Géométrie de l’Interaction et Sémantique Dénotationnelle. Thèse de doctorat, Université Aix-Marseille II.Google Scholar
Girard, J.-Y. (1989). Geometry of interaction I: interpretation of system F. In: Logic Colloquium’88, North-Holland, Amsterdam, 221–260.CrossRefGoogle Scholar
Girard, J.-Y. (1995). Geometry of interaction III: accommodating the additives. In: Advances in Linear Logic, LNS, vol. 222, Camridge University Press, UK, 329–389.CrossRefGoogle Scholar
Girard, J.-Y. (2011). Geometry of interaction V: logic in the hyperfinite factor. Theoretical Computer Science 412 (20) 1860–1883 CrossRefGoogle Scholar
Haghverdi, E. and Scott, P. (2006). A categorical model for the geometry of interaction. Theoretical Computer Science 350 (2–3) 252–274.CrossRefGoogle Scholar
Haghverdi, E. and Scott, P. (2011). Geometry of interaction and the dynamics of proof reduction: a tutorial. In: New Structures in Physics, Lectures Notes in Physics, 339–397.Google Scholar
Hamano, M. (2018). Geometry of interaction for MALL via Hughes-vanGlabbeek proof-nets. ACM Transactions on Computational Logic 19 (4) 1–25:38.CrossRefGoogle Scholar
Hamano, M. and Takemura, R. (2008). An indexed system for multiplicative additive polarized linear logic. In: Proceedings of CSL’08, LNCS, vol. 5213, 262–277.CrossRefGoogle Scholar
Joyal, A., Street, R. and Verity, D. (1996). Traced monoidal categories. Mathematical Proceedings of the Cambridge Philosophical Society 119, 447–468.CrossRefGoogle Scholar
Seiller, T. (2016). Interaction graphs: additives. Annals of Pure and Applied Logic 167, 95–154.CrossRefGoogle Scholar