The shuffle Hopf algebra and noncommutative full completeness
- 1 December 1998
- journal article
- Published by Cambridge University Press (CUP) in The Journal of Symbolic Logic
- Vol. 63 (4) , 1413-1436
Abstract
We present a full completeness theorem for the multiplicative fragment of a variant of noncommutative linear logic, Yetter'scyclic linear logic(CyLL). The semantics is obtained by interpreting proofs as dinatural transformations on a category of topological vector spaces, these transformations being equivariant under certain actions of a noncocommutative Hopf algebra called theshuffle algebraMultiplicative sequents are assigned a vector space of such dinaturals, and we show that this space has as a basis the denotations of cut-free proofs in CyLL + MIX. This can be viewed as a fully faithful representation of a free *-autonomous category, canonically enriched over vector spaces.This paper is a natural extension of the authors' previous work, “Linear Läuchli Semantics”, where a similar theorem is obtained for the commutative logic MLL + MIX. In that paper, we interpret proofs as dinaturals which are invariant under certain actions of the additive group of integers. Here we also present a simplification of that work by showing that the invariance criterion is actually a consequence of dinaturality. The passage from groups to Hopf algebras in this paper corresponds to the passage from commutative to noncommutative logic. However, in our noncommutative setting, one must still keep the invariance condition on dinaturals.Keywords
This publication has 26 references indexed in Scilit:
- Game Semantics1997
- Semantics of Interaction: an Introduction to Game Semantics1997
- Hopf algebras and linear logicMathematical Structures in Computer Science, 1996
- Appendix: Separability of tensor in Chu categories of vector spacesMathematical Structures in Computer Science, 1996
- The mix ruleMathematical Structures in Computer Science, 1994
- Linear logic, coherence and dinaturalityTheoretical Computer Science, 1993
- Hopf Algebras of Combinatorial StructuresCanadian Journal of Mathematics, 1993
- The system F of variable types, fifteen years laterTheoretical Computer Science, 1986
- Une théorie combinatoire des séries formellesAdvances in Mathematics, 1981
- Adjointness in FoundationsDialectica, 1969