BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Talks.cam//talks.cam.ac.uk//
X-WR-CALNAME:Talks.cam
BEGIN:VEVENT
SUMMARY:A link between lambda calculus and maps  - Noam Zeilberger\, MSR-I
 NRIA Joint Centre
DTSTART:20141007T090000Z
DTEND:20141007T100000Z
UID:TALK55094@talks.cam.ac.uk
CONTACT:Microsoft Research Cambridge Talks Admins
DESCRIPTION:In the talk\, I will report on a surprising and still quite my
 sterious/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 (be
 ta-)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 vari
 ables are used strictly follows a last-in\, first-out discipline (in the s
 ense that lambda corresponds to a "push"). I will begin by describing a si
 mple type system that characterizes the normal planar lambda terms\, as we
 ll as a planar diagrammatic syntax for such terms based on the machinery o
 f string diagrams. Then I will review the definition of rooted planar maps
 \, and Tutte's (1968) procedure for decomposing rooted planar maps by numb
 er 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 re
 playing Tutte's analysis in lambda calculus. 
LOCATION:Small Lecture Theatre\, Microsoft Research Ltd\, 21 Station Road\
 , Cambridge\, CB1 2FB
END:VEVENT
END:VCALENDAR