NZNoam Zeilberger

Noam Zeilberger

*This is an algorithmically generated author record based on publicly available information.

Current Organizations / Institutes

The organizations/institutes from the scholar's latest article

Previous Organizations / Institutes

The organizations / institutes from the scholar's other articles in the past ten years


Noam Zeilberger has a total of 4 co-authors. Here are the top co-authors by number of shared publications:


Latest Publications

  • Open Access

    Sampling β-normal linear λ-terms

    by Olivier Bodini, Alexandros Singh, Noam Zeilberger

    Leveraging our recent work on the enumeration of β-redices in closed linear λ-terms, we present an algorithm for sampling β-normal closed linear λ-terms and their corresponding maps. Such terms correspond to proofs of tautologies in implicational linear logic and their generation is of interest in various domains, including the testing of linear logic theorem provers.

  • Open Access

    Connected Chord Diagrams and Bridgeless Maps

    by Julien Courtiel, Karen Yeats, Noam Zeilberger

    We present a surprisingly new connection between two well-studied combinatorial classes: rooted connected chord diagrams on one hand, and rooted bridgeless combinatorial maps on the other hand. We describe a bijection between these two classes, which naturally extends to indecomposable diagrams and general rooted maps. As an application, this bijection provides a simplifying framework for some technical quantum field theory work realized by some of the authors. Most notably, an important but technical parameter naturally translates to vertices at the level of maps. We also give a combinatorial proof to a formula which previously resulted from a technical recurrence, and with similar ideas we prove a conjecture of Hihn. Independently, we revisit an equation due to Arquès and Béraud for the generating function counting rooted maps with respect to edges and vertices, giving a new bijective interpretation of this equation directly on indecomposable chord diagrams, which moreover can be specialized to connected diagrams and refined to incorporate the number of crossings. Finally, we explain how these results have a simple application to the combinatorics of lambda calculus, verifying the conjecture that a certain natural family of lambda terms is equinumerous with bridgeless maps.


  • Open Access

    A sequent calculus for a semi-associative law

    by Noam Zeilberger

    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 $Y_n$.Comment: This article is an extended version of a paper presented at FSCD 2017. [v2: minor rev] arXiv admin note: text overlap with arXiv:1701.02917


  • Open Access

    Connected chord diagrams and bridgeless maps

    by Julien Courtiel, Karen Yeats, Noam Zeilberger

    We present a surprisingly new connection between two well-studied combinatorial classes: rooted connected chord diagrams on one hand, and rooted bridgeless combinatorial maps on the other hand. We describe a bijection between these two classes, which naturally extends to indecomposable diagrams and general rooted maps. As an application, this bijection provides a simplifying framework for some technical quantum field theory work realized by some of the authors. Most notably, an important but technical parameter naturally translates to vertices at the level of maps. We also give a combinatorial proof to a formula which previously resulted from a technical recurrence, and with similar ideas we prove a conjecture of Hihn. Independently, we revisit an equation due to Arqu\`es and B\'eraud for the generating function counting rooted maps with respect to edges and vertices, giving a new bijective interpretation of this equation directly on indecomposable chord diagrams, which moreover can be specialized to connected diagrams and refined to incorporate the number of crossings. Finally, we explain how these results have a simple application to the combinatorics of lambda calculus, verifying the conjecture that a certain natural family of lambda terms is equinumerous with bridgeless maps.

  • Open Access

    Focusing and higher-order abstract syntax

    by Noam Zeilberger

    Focusing is a proof-search strategy, originating in linear logic, that elegantly eliminates inessential nondeterminism, with one byproduct being a correspondence between focusing proofs and programs with explicit evaluation order. Higher-order abstract syntax (HOAS) is a technique for representing higher-order programming language constructs (e.g., λ's) by higher-order terms at the"meta-level", thereby avoiding some of the bureaucratic headaches of first-order representations (e.g., capture-avoiding substitution). This paper begins with a fresh, judgmental analysis of focusing for intuitionistic logic (with a full suite of propositional connectives), recasting the "derived rules" of focusing as iterated inductive definitions . This leads to a uniform presentation, allowing concise, modular proofs of the identity and cut principles. Then we show how this formulation of focusing induces, through the Curry-Howard isomorphism, a new kind of higher-order encoding of abstract syntax: functions are encoded by maps from patterns to expressions. Dually, values are encoded as patterns together with explicit substitutions . This gives us pattern-matching "for free", and lets us reason about a rich type system with minimal syntactic overhead. We describe how to translate the language and proof of type safety almost directly into Coq using HOAS, and finally, show how the system's modular design pays off in enabling a very simple extension with recursion and recursive types.