Abstract

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.