BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//talks.cam.ac.uk//v3//EN
BEGIN:VTIMEZONE
TZID:Europe/London
BEGIN:DAYLIGHT
TZOFFSETFROM:+0000
TZOFFSETTO:+0100
TZNAME:BST
DTSTART:19700329T010000
RRULE:FREQ=YEARLY;BYMONTH=3;BYDAY=-1SU
END:DAYLIGHT
BEGIN:STANDARD
TZOFFSETFROM:+0100
TZOFFSETTO:+0000
TZNAME:GMT
DTSTART:19701025T020000
RRULE:FREQ=YEARLY;BYMONTH=10;BYDAY=-1SU
END:STANDARD
END:VTIMEZONE
BEGIN:VEVENT
CATEGORIES:Microsoft Research Cambridge\, public talks
SUMMARY:A link between lambda calculus and maps - Noam Ze
ilberger\, MSR-INRIA Joint Centre
DTSTART;TZID=Europe/London:20141007T100000
DTEND;TZID=Europe/London:20141007T110000
UID:TALK55094AThttp://talks.cam.ac.uk
URL:http://talks.cam.ac.uk/talk/index/55094
DESCRIPTION:In the talk\, I will report on a surprising and st
ill quite mysterious/tenuous connection between la
mbda 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 cal
culus 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 "pl
anar" if the order in which variables are used str
ictly 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 tha
t characterizes the normal planar lambda terms\, a
s well as a planar diagrammatic syntax for such te
rms based on the machinery of string diagrams. The
n I will review the definition of rooted planar ma
ps\, 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 i
n lambda calculus.
LOCATION:Small Lecture Theatre\, Microsoft Research Ltd\, 2
1 Station Road\, Cambridge\, CB1 2FB
CONTACT:Microsoft Research Cambridge Talks Admins
END:VEVENT
END:VCALENDAR