@inproceedings{be89f72101ca4278951ac65b8c297d4d,
title = "A sequent calculus for a semi-Associative law",
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.",
keywords = "Coherence theorem, Combinatorics, Proof theory, Substructural logic",
author = "Noam Zeilberger",
note = "Publisher Copyright: {\textcopyright} Noam Zeilberger.; 2nd International Conference on Formal Structures for Computation and Deduction, FSCD 2017 ; Conference date: 03-09-2017 Through 09-09-2017",
year = "2017",
month = sep,
day = "1",
doi = "10.4230/LIPIcs.FSCD.2017.33",
language = "English",
series = "Leibniz International Proceedings in Informatics, LIPIcs",
publisher = "Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing",
editor = "Dale Miller",
booktitle = "2nd International Conference on Formal Structures for Computation and Deduction, FSCD 2017",
}