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:Category Theory Seminar
SUMMARY:The Algebra of Directed Acyclic Graphs - Marco Dev
esas Campos\, Computer Laboratory\, Cambridge
DTSTART;TZID=Europe/London:20120522T141500
DTEND;TZID=Europe/London:20120522T151500
UID:TALK38082AThttp://talks.cam.ac.uk
URL:http://talks.cam.ac.uk/talk/index/38082
DESCRIPTION:In this talk I'll present the work that Marcelo Fi
ore and I did on a finitary algebraic characterisa
tion of directed acyclic graphs (dags).\n\nWe expr
ess the algebra of dags as a product and permutati
on category (PROP)\, a symmetric monoidal variant
of Lawvere theories. In the talk\, I'll survey sim
ple examples of symmetric monoidal theories and th
e PROPs they give rise to and explain how they can
be combined to express the dag structure.\n\nSpec
ifically\, I'll characterise the algebra of dags a
s the PROP generated by the theory of bialgebras
that are commutative\, co-commutative and degenera
te\, together with a generic endomorphism. The cru
x of the problem lies in how to combine two differ
ent algebras without the aid of a distributive law
\, as we commonly have for monads. Technically\, t
his is circumvented by a careful choice and analys
is of canonical forms. I'll end by showing how our
work can be further generalised to the cases wher
e the dag links are weighted by natural and intege
r numbers.\n\nAs for practical applications\, this
work originated from a question by Robin Milner i
n the context of distributed systems. He wished to
extend of his bigraphical model to place graphs t
hat allowed for sharing\, thus generalising them f
rom tree-like structures to dags. With this work w
e provide the necessary axioms to formalise this g
eneralisation.\n\n
LOCATION:MR5\, Centre for Mathematical Sciences
CONTACT:Julia Goedecke
END:VEVENT
END:VCALENDAR