Counting isomorphism classes of $β$-normal linear lambda terms
Counting isomorphism classes of $β$-normal linear lambda terms
复制标题
计算 $β$-正规线性 lambda 项的同构类
DOI：
--
复制
发表时间：
2015
期刊：
影响因子：
--
通讯作者：
N. Zeilberger
中科院分区：
文献类型：
--
作者：
N. Zeilberger
Lambda演算的不同片段和不同嵌入图族之间的意外联系(也称为。“map”)引发了枚举$\beta$-正规线性Lambda项的问题。本文借助于Arques和Beraud的一个定理，证明了直到相邻Lambda抽象自由交换的正规线性Lambda项的序列计数同构类与定向曲面上有根映射的序列计数同构类重合(A000698).
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).