pith. sign in

arxiv: 1509.07596 · v1 · pith:QMJYHEPVnew · submitted 2015-09-25 · 💻 cs.LO · math.CO· math.LO

Counting isomorphism classes of β-normal linear lambda terms

classification 💻 cs.LO math.COmath.LO
keywords lambdabetaclassescountingisomorphismlinearnormalterms
0
0 comments X
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.