Skip to main navigation Skip to search Skip to main content

A sequent calculus for a semi-Associative law

  • University of Birmingham

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

4 Citations (Scopus)

Abstract

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, tree 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. One combinatorial application of this coherence theorem is a new proof of the Tutte-Chapoton formula for the number of intervals in the Tamari lattice Yn. Elsewhere, we have also used the sequent calculus and the coherence theorem to build a surprising bijection between intervals of the Tamari order and a natural fragment of lambda calculus, consisting of the β-normal planar lambda terms with no closed proper subterms.

Original languageEnglish
Title of host publication2nd International Conference on Formal Structures for Computation and Deduction, FSCD 2017
EditorsDale Miller
PublisherSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
ISBN (Electronic)9783959770477
DOIs
Publication statusPublished - 1 Sept 2017
Externally publishedYes
Event2nd International Conference on Formal Structures for Computation and Deduction, FSCD 2017 - Oxford, United Kingdom
Duration: 3 Sept 2017 → 9 Sept 2017

Publication series

NameLeibniz International Proceedings in Informatics, LIPIcs
Volume84
ISSN (Print)1868-8969

Conference

Conference2nd International Conference on Formal Structures for Computation and Deduction, FSCD 2017
Country/TerritoryUnited Kingdom
CityOxford
Period3/09/17 → 9/09/17

Keywords

  • Coherence theorem
  • Combinatorics
  • Proof theory
  • Substructural logic

Fingerprint

Dive into the research topics of 'A sequent calculus for a semi-Associative law'. Together they form a unique fingerprint.

Cite this