The Algebra of Directed Acyclic Graphs

Add to your list(s) Download to your calendar using vCal

• Marco Devesas Campos, Computer Laboratory, Cambridge
• Tuesday 22 May 2012, 14:15-15:15
• MR5, Centre for Mathematical Sciences.

If you have a question about this talk, please contact Julia Goedecke.

In this talk I’ll present the work that Marcelo Fiore and I did on a finitary algebraic characterisation of directed acyclic graphs (dags).

We express the algebra of dags as a product and permutation category (PROP), a symmetric monoidal variant of Lawvere theories. In the talk, I’ll survey simple examples of symmetric monoidal theories and the PRO Ps they give rise to and explain how they can be combined to express the dag structure.

Specifically, I’ll characterise the algebra of dags as the PROP generated by the theory of bialgebras that are commutative, co-commutative 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, this is circumvented by a careful choice and analysis of canonical forms. I’ll end by showing how our work can be further generalised to the cases where the dag links are weighted by natural and integer numbers.

As for practical applications, this work originated from a question by Robin Milner in the context of distributed systems. He wished to extend of his bigraphical model to place graphs that allowed for sharing, thus generalising them from tree-like structures to dags. With this work we provide the necessary axioms to formalise this generalisation.

This talk is part of the Category Theory Seminar series.

This talk is included in these lists:

• All CMS events
• All Talks (aka the CURE list)
• CMS Events
• Category Theory Seminar
• DPMMS Lists
• DPMMS Pure Maths Seminar
• DPMMS info aggregator
• MR5, Centre for Mathematical Sciences
• School of Physical Sciences

Note that ex-directory lists are not shown.