{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,7,30]],"date-time":"2025-07-30T15:37:12Z","timestamp":1753889832451,"version":"3.41.2"},"reference-count":1,"publisher":"Centre pour la Communication Scientifique Directe (CCSD)","license":[{"start":{"date-parts":[[2015,9,25]],"date-time":"2015-09-25T00:00:00Z","timestamp":1443139200000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/arxiv.org\/licenses\/nonexclusive-distrib\/1.0"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"abstract":"<jats:p>A rooted planar map is a connected graph embedded in the 2-sphere, with one\nedge marked and assigned an orientation. A term of the pure lambda calculus is\nsaid to be linear if every variable is used exactly once, normal if it contains\nno beta-redexes, and planar if it is linear and the use of variables moreover\nfollows a deterministic stack discipline. We begin by showing that the sequence\ncounting normal planar lambda terms by a natural notion of size coincides with\nthe sequence (originally computed by Tutte) counting rooted planar maps by\nnumber of edges. Next, we explain how to apply the machinery of string diagrams\nto derive a graphical language for normal planar lambda terms, extracted from\nthe semantics of linear lambda calculus in symmetric monoidal closed categories\nequipped with a linear reflexive object or a linear reflexive pair. Finally,\nour main result is a size-preserving bijection between rooted planar maps and\nnormal planar lambda terms, which we establish by explaining how Tutte\ndecomposition of rooted planar maps (into vertex maps, maps with an isthmic\nroot, and maps with a non-isthmic root) may be naturally replayed in linear\nlambda calculus, as certain surgeries on the string diagrams of normal planar\nlambda terms.<\/jats:p>","DOI":"10.2168\/lmcs-11(3:22)2015","type":"journal-article","created":{"date-parts":[[2016,11,21]],"date-time":"2016-11-21T13:46:02Z","timestamp":1479735962000},"source":"Crossref","is-referenced-by-count":6,"title":["A correspondence between rooted planar maps and normal planar lambda terms"],"prefix":"10.46298","volume":"Volume 11, Issue 3","author":[{"given":"Noam","family":"Zeilberger","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-0990-9611","authenticated-orcid":false,"given":"Alain","family":"Giorgetti","sequence":"additional","affiliation":[]}],"member":"25203","published-online":{"date-parts":[[2015,9,25]]},"reference":[{"key":"1060:not-found"}],"container-title":["Logical Methods in Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/lmcs.episciences.org\/1598\/pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/lmcs.episciences.org\/1598\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,4,11]],"date-time":"2023-04-11T20:07:38Z","timestamp":1681243658000},"score":1,"resource":{"primary":{"URL":"https:\/\/lmcs.episciences.org\/1598"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,9,25]]},"references-count":1,"URL":"https:\/\/doi.org\/10.2168\/lmcs-11(3:22)2015","relation":{"is-same-as":[{"id-type":"arxiv","id":"1408.5028","asserted-by":"subject"},{"id-type":"doi","id":"10.48550\/arXiv.1408.5028","asserted-by":"subject"}]},"ISSN":["1860-5974"],"issn-type":[{"type":"electronic","value":"1860-5974"}],"subject":[],"published":{"date-parts":[[2015,9,25]]},"article-number":"1598"}}