Counting isomorphism classes of β-normal linear lambda terms
classification
💻 cs.LO
math.COmath.LO
keywords
lambdabetaclassescountingisomorphismlinearnormalterms
read the original abstract
Unanticipated connections between different fragments of lambda calculus and different families of embedded graphs (a.k.a. "maps") motivate the problem of enumerating $\beta$-normal linear lambda terms. In this brief note, it is shown (by appeal to a theorem of Arqu\`es and Beraud) that the sequence counting isomorphism classes of $\beta$-normal linear lambda terms up to free exchange of adjacent lambda abstractions coincides with the sequence counting isomorphism classes of rooted maps on oriented surfaces (A000698).
This paper has not been read by Pith yet.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.