A correspondence between rooted planar maps and normal planar lambda terms

Noam Zeilberger 1 Alain Giorgetti 2, 3
2 CASSIS - Combination of approaches to the security of infinite states systems
FEMTO-ST - Franche-Comté Électronique Mécanique, Thermique et Optique - Sciences et Technologies (UMR 6174), Inria Nancy - Grand Est, LORIA - FM - Department of Formal Methods
Abstract : 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.
Type de document :
Article dans une revue
Logical Methods in Computer Science, Logical Methods in Computer Science Association, 2015, 11 (3:22), pp.1-39. 〈http://www.lmcs-online.org/ojs/viewarticle.php?id=1695&layout=abstract〉. 〈10.2168/LMCS-11(3:22)2015〉
Liste complète des métadonnées

https://hal.inria.fr/hal-01057269
Contributeur : Noam Zeilberger <>
Soumis le : vendredi 22 août 2014 - 09:17:00
Dernière modification le : vendredi 6 juillet 2018 - 15:06:10

Lien texte intégral

Identifiants

Citation

Noam Zeilberger, Alain Giorgetti. A correspondence between rooted planar maps and normal planar lambda terms. Logical Methods in Computer Science, Logical Methods in Computer Science Association, 2015, 11 (3:22), pp.1-39. 〈http://www.lmcs-online.org/ojs/viewarticle.php?id=1695&layout=abstract〉. 〈10.2168/LMCS-11(3:22)2015〉. 〈hal-01057269〉

Partager

Métriques

Consultations de la notice

445