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:Logic and Semantics Seminar (Computer Laboratory)
SUMMARY:Incrementality xor currency for monotone fixed poi
nts - Michael Arntzenius\, University of Cambridge
DTSTART;TZID=Europe/London:20201016T140000
DTEND;TZID=Europe/London:20201016T150000
UID:TALK152581AThttp://talks.cam.ac.uk
URL:http://talks.cam.ac.uk/talk/index/152581
DESCRIPTION:https://youtu.be/OkX6YKSLNQ0\n\nMany problems can
be concisely expressed as finding the least fixed
point of a monotone map\, including graph reachabi
lity\, static analysis by abstract interpretation\
, regular expression matching\, and parsing. There
is a straightforward way to compute these fixpoin
ts: iterate the function. Unfortunately\, this is
inefficient\, for at least two reasons: first\, it
performs redundant work during each iteration\; s
econd\, it is inherently single-threaded.\n\nIn th
is talk\, I will show how to solve the first of th
ese problems using seminaive evaluation\, a techni
que that iterates to a fixed point faster by compu
ting only the differences between iterations. I wi
ll also discuss work in progress on the second pro
blem using a simple graph based model of concurren
t monotone computation. Unfortunately\, I do not k
now how to reconcile these two approaches and achi
eve an implementation strategy for monotone fixed
points that is both incremental and concurrent.
LOCATION:Online
CONTACT:Jamie Vicary
END:VEVENT
END:VCALENDAR