COOKIES: By using this website you agree that we can place Google Analytics Cookies on your device for performance monitoring. |

University of Cambridge > Talks.cam > Microsoft Research Cambridge, public talks > A link between lambda calculus and maps

## A link between lambda calculus and mapsAdd to your list(s) Download to your calendar using vCal - Noam Zeilberger, MSR-INRIA Joint Centre
- Tuesday 07 October 2014, 10:00-11:00
- Small Lecture Theatre, Microsoft Research Ltd, 21 Station Road, Cambridge, CB1 2FB.
If you have a question about this talk, please contact Microsoft Research Cambridge Talks Admins. This event may be recorded and made available internally or externally via http://research.microsoft.com. Microsoft will own the copyright of any recordings made. If you do not wish to have your image/voice recorded please consider this before attending In the talk, I will report on a surprising and still quite mysterious/tenuous connection between lambda calculus and the theory of maps on surfaces (described in an arxiv draft with Alain Giorgetti: arxiv.org/abs/1408.5028). A term of the lambda calculus is standardly said to be (beta-)normal if it is fully evaluated, and linear if every variable is used exactly once. Let us moreover call it “planar” if the order in which variables are used strictly follows a last-in, first-out discipline (in the sense that lambda corresponds to a “push”). I will begin by describing a simple type system that characterizes the normal planar lambda terms, as well as a planar diagrammatic syntax for such terms based on the machinery of string diagrams. Then I will review the definition of rooted planar maps, and Tutte’s (1968) procedure for decomposing rooted planar maps by number of edges. Finally, I will show how to build a bijection between rooted planar maps and normal planar lambda terms (with one free variable) by replaying Tutte’s analysis in lambda calculus. This talk is part of the Microsoft Research Cambridge, public talks series. ## This talk is included in these lists:- All Talks (aka the CURE list)
- Cambridge Big Data
- Cambridge University Engineering Department Talks
- Centre for Smart Infrastructure & Construction
- Featured lists
- Guy Emerson's list
- Methodology in design research
- Microsoft Research Cambridge, public talks
- PMRFPS's
- School of Technology
- Small Lecture Theatre, Microsoft Research Ltd, 21 Station Road, Cambridge, CB1 2FB
- ndk22's list
- rp587
Note that ex-directory lists are not shown. |
## Other listsSciScreen Department of Earth Sciences Seminars (downtown) Pembroke College Corporate Partnership Talks## Other talksOn Classical Tractability of Quantum Schur Sampling Locomotion in extinct giant kangaroos? Hopping for resolution. Ethics for the working mathematician, seminar 9 CANCELLED NatHistFest: the 99th Conversazione and exhibition on the wonders of the natural world. Communicating Your Research to the Wider World |