Reference. A sequent calculus for a semi-associative law

Noam Zeilberger · · lambek · DOI · arXiv
We introduce a sequent calculus with a simple restriction of Lambek’s product rules that precisely captures the classical Tamari order, i.e., the partial order on fully-bracketed words (equivalently, binary trees) induced by a semi-associative law (equivalently, right rotation). We establish a focusing property for this sequent calculus (a strengthening of cut-elimination), which yields the following coherence theorem: every valid entailment in the Tamari order has exactly one focused derivation. We then describe two main applications of the coherence theorem, including: 1. A new proof of the lattice property for the Tamari order, and 2. A new proof of the Tutte-Chapoton formula for the number of intervals in the Tamari lattice 𝑌𝑛.

Cite

Cite as @zeilberger-2019-a (helia, typst) · \cite{zeilberger-2019-a} (LaTeX)
BibTeX
bibtex · 1 line
@article{zeilberger-2019-a, title={A sequent calculus for a semi-associative law}, volume={Volume 15, Issue 1}, ISSN={1860-5974}, url={http://dx.doi.org/10.23638/lmcs-15(1:9)2019}, DOI={10.23638/lmcs-15(1:9)2019}, journal={Logical Methods in Computer Science}, publisher={Centre pour la Communication Scientifique Directe (CCSD)}, author={Zeilberger, Noam}, year={2019}, month=Feb }
hayagriva YAML (typst)
yaml · 14 lines
zeilberger-2019-a:
  type: article
  title: A sequent calculus for a semi-associative law
  author: Zeilberger, Noam
  date: 2019-02
  url: http://dx.doi.org/10.23638/lmcs-15(1:9)2019
  serial-number:
    doi: 10.23638/lmcs-15(1:9)2019
    issn: 1860-5974
  parent:
    type: periodical
    title: Logical Methods in Computer Science
    publisher: Centre pour la Communication Scientifique Directe (CCSD)
    volume: Volume 15, Issue 1
Cited by (5)

The Sequent Calculus of Skew Monoidal Categories uustalu-2020-the

Szlachányi’s skew monoidal categories are a well-motivated variation of monoidal categories in which the unitors and associator are not required to be natural isomorphisms, but merely natural transformations in a particular direction. We present a sequent calculus for skew monoidal categories, building on the recent formulation by one of the authors of a sequent calculus for the Tamari order (skew semigroup categories). In this calculus, antecedents consist of a stoup (an optional formula) followed by a context, and the connectives behave like in the standard monoidal sequent calculus except that the left rules may only be applied in stoup position. We prove that this calculus is sound and complete with respect to existence of maps in the free skew monoidal category, and moreover that it captures equality of maps once a suitable equivalence relation is imposed on derivations. We then identify a subsystem of focused derivations and establish that it contains exactly one canonical representative from each equivalence class. This coherence theorem leads directly to simple procedures for deciding equality of maps in the free skew monoidal category and for enumerating any homset without duplicates. Finally, and in the spirit of Lambek’s work, we describe the close connection between this proof-theoretic analysis and Bourke and Lack’s recent characterization of skew monoidal categories as left representable skew multicategories. We have formalized this development in the dependently typed programming language Agda.
DOI · arXiv

Proof Theory of Partially Normal Skew Monoidal Categories uustalu-2021-proof

DOI · arXiv

Deductive Systems and Coherence for Skew Prounital Closed Categories uustalu-2021-deductive

DOI · arXiv

Eilenberg-Kelly Reloaded uustalu-2020-eilenberg

DOI

A theory of linear typings as flows on 3-valent graphs zeilberger-2018-a

DOI · arXiv
Cites 44 works (3 here)
With notes (3)

Linear lambda terms as invariants of rooted trivalent maps zeilberger-2016-linear

The main aim of the paper is to give a simple and conceptual account for the correspondence (originally described by Bodini, Gardy, and Jacquot) between α-equivalence classes of closed linear lambda terms and isomorphism classes of rooted trivalent maps on compact-oriented surfaces without boundary, as an instance of a more general correspondence between linear lambda terms with a context of free variables and rooted trivalent maps with a boundary of free edges. We begin by recalling a familiar diagrammatic representation for linear lambda terms, while at the same time explaining how such diagrams may be read formally as a notation for endomorphisms of a reflexive object in a symmetric monoidal closed (bi)category. From there, the “easy” direction of the correspondence is a simple forgetful operation which erases annotations on the diagram of a linear lambda term to produce a rooted trivalent map. The other direction views linear lambda terms as complete invariants of their underlying rooted trivalent maps, reconstructing the missing information through a Tutte-style topological recurrence on maps with free edges. As an application in combinatorics, we use this analysis to enumerate bridgeless rooted trivalent maps as linear lambda terms containing no closed proper subterms, and conclude by giving a natural reformulation of the Four Color Theorem as a statement about typing in lambda calculus.
PDF · DOI · arXiv · pldb

On the unity of duality zeilberger-2008-on

DOI

The mathematics of sentence structure lambek58

DOI
External (41)
zeilberger-2019-a reference entries/refs/zeilberger-2019-a/zeilberger-2019-a.hel