BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Talks.cam//talks.cam.ac.uk//
X-WR-CALNAME:Talks.cam
BEGIN:VEVENT
SUMMARY:The Algebra of Directed Acyclic Graphs - Marco Devesas Campos\, Co
 mputer Laboratory\, Cambridge
DTSTART:20120522T131500Z
DTEND:20120522T141500Z
UID:TALK38082@talks.cam.ac.uk
CONTACT:Julia Goedecke
DESCRIPTION:In this talk I'll present the work that Marcelo Fiore and I di
 d on a finitary algebraic characterisation of directed acyclic graphs (dag
 s).\n\nWe express the algebra of dags as a product and permutation categor
 y (PROP)\, a symmetric monoidal variant of Lawvere theories. In the talk\,
  I'll survey simple examples of symmetric monoidal theories and the PROPs 
 they give rise to and explain how they can be combined to express the dag 
 structure.\n\nSpecifically\, I'll characterise the algebra of dags as the 
 PROP generated by the  theory of bialgebras that are commutative\, co-comm
 utative and degenerate\, together with a generic endomorphism. The crux of
  the problem lies in how to combine two different algebras without the aid
  of a distributive law\, as we commonly have for monads. Technically\, thi
 s is circumvented by a careful choice and analysis of canonical forms. I'l
 l end by showing how our work can be further generalised to the cases wher
 e the dag links are weighted by natural and integer numbers.\n\nAs for pra
 ctical applications\, this work originated from a question by Robin Milner
  in the context of distributed systems. He wished to extend of his bigraph
 ical model to place graphs that allowed for sharing\, thus generalising th
 em from tree-like structures to dags. With this work we provide the necess
 ary axioms to formalise this generalisation.\n\n
LOCATION:MR5\, Centre for Mathematical Sciences
END:VEVENT
END:VCALENDAR