University of Cambridge > Talks.cam > Category Theory Seminar > The Algebra of Directed Acyclic Graphs

The Algebra of Directed Acyclic Graphs

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

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.

Tell a friend about this talk:

This talk is included in these lists:

Note that ex-directory lists are not shown.

 

© 2006-2019 Talks.cam, University of Cambridge. Contact Us | Help and Documentation | Privacy and Publicity