Reference. A sequent calculus for a semi-associative law
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
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.
Proof Theory of Partially Normal Skew Monoidal Categories uustalu-2021-proof
Deductive Systems and Coherence for Skew Prounital Closed Categories uustalu-2021-deductive
Eilenberg-Kelly Reloaded uustalu-2020-eilenberg
A theory of linear typings as flows on 3-valent graphs zeilberger-2018-a
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.
On the unity of duality zeilberger-2008-on
External (41)
- The On-Line Encyclopedia of Integer Sequences (2019)
- Skew monoidal categories and skew multicategories (2018)
- Planar triangulations, bridgeless planar maps and Tamari intervals (2018)
- A sequent calculus for the Tamari order (2017)
- A sequent calculus for a semi-associative law (FSCD 2017) (2017)
- Permutohedra and Associahedra (2016)
- A correspondence between rooted planar maps and normal planar lambda terms (2015)
- Triangulations, orientals, and skew monoidal categories (2014)
- Coherence for Skew-Monoidal Categories (2014)
- Asymptotics and random sampling for BCI and BCK lambda terms (2013)
- The Logic of Categorial Grammars: A Deductive Account of Natural Language Syntax and Semantics (2012)
- Skew-monoidal categories and bialgebroids (2012)
- Associahedra, tamari lattices and related structures : Tamari memorial festschrift (2012)
- Focus-preserving Embeddings of Substructural Logics in Intuitionistic Logic (2010)
- Intervals in Catalan lattices and realizers of triangulations (2009)
- Queue logic: An undisplayable logic? (2009)
- Sur le nombre d'intervalles dans les treillis de Tamari (2006)
- Graphs on Surfaces and Their Applications (2004)
- Higher Operads, Higher Categories (2004)
- Description trees and Tutte formulas (2003)
- Axiomatic Rewriting Theory VI: Residual Theory Revisited (2002)
- Structural cut elimination: I. Intuitionistic and classical logic (2000)
- Representable multicategories (2000)
- The associative law, or the anatomy of rotations in binary trees (talk) (1993)
- Logic Programming with Focusing Proofs in Linear Logic (1992)
- Rotation distance, triangulations, and hyperbolic geometry (1988)
- A graphic theory of associativity and wordchain patterns (1982)
- Counting rooted maps by genus III: Nonseparable maps (1975)
- Problems of associativity: A simple proof for the lattice property of systems ordered by a semi-associative law (1972)
- Coherence for associativity not an isomorphism (1972)
- Deductive systems and categories II. Standard constructions and closed categories (1969)
- Investigations into logical deductions (Collected Papers of Gerhard Gentzen) (1969)
- Problèmes d'associativité: Une structure de treillis finis induite par une loi demi-associative (1967)
- Sur quelques problèmes d'associativité (1964)
- Homotopy associativity of 𝐻-spaces (1963)
- Natural associativity and commutativity (1963)
- Problèmes d 'associativité des monoïdes et problèmes des mots pour les groupes (1963)
- A Census of Planar Triangulations (1962)
- On the calculus of syntactic types (1961)
- The Immersibility of a Semigroup into a Group (1951)
- Monoïdes préordonnés et chaînes de Malcev (thèse) (1951)