Semantics for a Lambda Calculus for String Diagrams

Bert Lindenhovius (1) , Michael Mislove (1) , Vladimir Zamdzhiev (2)

1 Tulane University
2 MOCQUA - Designing the Future of Computational Models

Linear/non-linear (LNL) models, as described by Benton, soundly model a LNL term calculus and LNL logic closely related to intuitionistic linear logic. Every such model induces a canonical enrichment that we show soundly models a LNL lambda calculus for string diagrams, introduced by Rios and Selinger (with primary application in quantum computing). Our abstract treatment of this language leads to simpler concrete models compared to those presented so far. We also extend the language with general recursion and prove soundness. Finally, we present an adequacy result for the diagram-free fragment of the language which corresponds to a modified version of Benton and Wadler's adjoint calculus with recursion. In keeping with the purpose of the special issue, we also describe the influence of Samson Abramsky's research on these results, and on the overall project of which this is a part.

Domaines: Logique en informatique [cs.LO]

Bert Lindenhovius, Michael Mislove, Vladimir Zamdzhiev. Semantics for a Lambda Calculus for String Diagrams. 2020. ⟨hal-03018467⟩