Normalization and sub-formula property for Lambek with product and PCMLL -- Partially Commutative Multiplicative Linear Logic

Maxime Amblard (1) , Christian Retoré (2)

1 SEMAGRAMME - Semantic Analysis of Natural Language
2 LaBRI - Laboratoire Bordelais de Recherche en Informatique

This paper establishes the normalisation of natural deduction or lambda calculus formulation of Intuitionistic Non Commutative Logic --- which involves both commutative and non commutative connectives. This calculus first introduced by de Groote and as opposed to the classical version by Abrusci and Ruet admits a full entropy which allow order to be relaxed into any suborder. Our result also includes, as a special case, the normalisation of natural deduction the Lambek calculus with product, which is unsurprising but yet unproved. Regarding Intuitionistic Non Commutative Logic with full entropy does not have up to now a proof net syntax, and that for linguistic applications, sequent calculi which are only more or less equivalent to natural deduction, are not convenient because they lack the standard Curry-Howard isomorphism.

Mots clés: Logic; Intuitionistic Non Commutative Logic; Lambek calculus; normalisation

Domaines: Linguistique; Logique en informatique [cs.LO]; Théorie et langage formel [cs.FL]

Maxime Amblard, Christian Retoré. Normalization and sub-formula property for Lambek with product and PCMLL -- Partially Commutative Multiplicative Linear Logic. 2007. ⟨hal-00941206⟩