University of Birmingham > Talks@bham > Theoretical computer science seminar > 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
- Friday 10 October 2014, 12:00-13:00
- CS 217.
If you have a question about this talk, please contact Neel Krishnaswami. 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 Theoretical computer science seminar series. ## This talk is included in these lists:- CS 217
- Computer Science Departmental Series
- Computer Science Distinguished Seminars
- Theoretical computer science seminar
Note that ex-directory lists are not shown. |
## Other listsIMA West Midlands Branch Reading Group in Combinatorics and Probability Speech Recognition by Synthesis Seminars## Other talksSchool Seminar School Seminar An attack on ECDSA using lattice techniques Role of Mechanics and Geometry in Cellular Information Processing TBA Multi-dimensional vector assignment problems (MVA) : Complexity, Approximation and Algorithms |