BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//talks.bham.ac.uk//v3//EN
BEGIN:VEVENT
CATEGORIES:Theoretical computer science seminar
SUMMARY:A link between lambda calculus and maps - Noam Zei
lberger
DTSTART:20141010T110000Z
DTEND:20141010T120000Z
UID:TALK1557AT
URL:/talk/index/1557
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). \n\nA term of the lambd
a calculus is standardly said to be (beta-)normal
if it is fully evaluated\, and linear if every var
iable is used exactly once. Let us moreover call
it "planar" if the order in which variables are us
ed strictly follows a last-in\, first-out discipli
ne (in the sense that lambda corresponds to a "pus
h"). I will begin by describing a simple type sys
tem that characterizes the normal planar lambda te
rms\, as well as a planar diagrammatic syntax for
such terms based on the machinery of string diagra
ms. \n\nThen I will review the definition of root
ed 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 b
etween rooted planar maps and normal planar lambda
terms (with one free variable) by replaying Tutte
's analysis in lambda calculus.
LOCATION:CS 217
CONTACT:Neel Krishnaswami
END:VEVENT
END:VCALENDAR