Abstract
Thirty years ago, I introduced a non commutative variant of classical linear logic, called pomset logic, issued from a particular denotational se- mantics or categorical interpretation of linear logic known as coherence spaces. In addition to the multiplicative connectives of linear logic, pomset logic includes a non-commutative connective, ”<” called before, which is associative and self-dual: (A < B)⊥ = A⊥ < B⊥ (observe that there is no swapping), and pomset logic handles Partially Ordered Multisets of for- mulas. This classical calculus enjoys a proof net calculus, cut-elimination, denotational semantics, but had no sequent calculus, despite my many attempts and the study of closely related deductive systems like the cal- culus of structures. At the same period, Alain Lecomte introduced me to Lambek calculus and grammars. We defined a grammatical formalism based on pomset logic, with partial proof nets as the deductive systems for parsing-as-deduction, with a lexicon mapping words to partial proof nets. The study of pomset logic and of its grammatical applications has been out of the limelight for several years, in part because computational lin- guists were not too keen on proof nets. However, recently Sergey Slavnov found a sequent calculus for pomset logic, and reopened the study of pomset logic. In this paper we shall present pomset logic including both published and unpublished material. Just as for Lambek calculus, Pomset logic also is a non commutative variant of linear logic — although Lam- bek calculus appeared 30 years before linear logic ! — and as in Lambek calculus it may be used as a grammar. Apart from this the two calculi are quite different, but perhaps the algebraic presentation we give here, with terms and the semantic correctness criterion, is closer to Lambek’s view.