A correspondence between rooted planar maps and normal planar lambda terms
A correspondence between rooted planar maps and normal planar lambda terms
复制标题
有根平面映射与普通平面 lambda 项之间的对应关系
DOI：
--
复制
发表时间：
2014
期刊：
影响因子：
--
通讯作者：
Alain Giorgetti
中科院分区：
文献类型：
--
作者：
N. Zeilberger;Alain Giorgetti
扎根平面图是嵌入在2个球体中的连接图，一个边缘标记并分配了方向。纯lambda演算的术语据说是线性的，如果每个变量完全使用一次，则不包含beta-redexes，并且平面是线性的，如果变量的使用以及变量的使用此外，则遵循确定性的堆栈学科。首先，我们通过自然的大小概念来表明对正常平面lambda术语计数的序列与序列（最初由Tutte计算）的序列相吻合，该序列按边数数来计数根平面图。接下来，我们说明如何应用弦图的机械来推导正常平面lambda术语的图形语言，这些术语是从配备有线性反射对象或线性反射对的对称单型封闭类别中从线性lambda conculus的语义中提取的。最后，我们的主要结果是在根部平面图和正常的平面lambda项之间进行尺寸保留大小的双歧射击，我们通过解释如何解释生根平面图的tutte分解（进入顶点映射，带有静脉的根部图，并用非 - 图形地图iSthmic root）可以自然地以线性lambda微积分重播，因为正常平面的弦图上的某些手术lambda条款。
A rooted planar map is a connected graph embedded in the 2-sphere, with one edge marked and assigned an orientation. A term of the pure lambda calculus is said to be linear if every variable is used exactly once, normal if it contains no beta-redexes, and planar if it is linear and the use of variables moreover follows a deterministic stack discipline. We begin by showing that the sequence counting normal planar lambda terms by a natural notion of size coincides with the sequence (originally computed by Tutte) counting rooted planar maps by number of edges. Next, we explain how to apply the machinery of string diagrams to derive a graphical language for normal planar lambda terms, extracted from the semantics of linear lambda calculus in symmetric monoidal closed categories equipped with a linear reflexive object or a linear reflexive pair. Finally, our main result is a size-preserving bijection between rooted planar maps and normal planar lambda terms, which we establish by explaining how Tutte decomposition of rooted planar maps (into vertex maps, maps with an isthmic root, and maps with a non-isthmic root) may be naturally replayed in linear lambda calculus, as certain surgeries on the string diagrams of normal planar lambda terms.
DOI：
10.1007/978-3-642-38164-5
发表时间：
2013
期刊：
--
影响因子：
--
作者：
B. Coecke;Luke Ong;P. Panangaden;S. Abramsky
通讯作者：
B. Coecke;Luke Ong;P. Panangaden;S. Abramsky