|COOKIES: By using this website you agree that we can place Google Analytics Cookies on your device for performance monitoring.|
The Algebra of Directed Acyclic Graphs
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:
Note that ex-directory lists are not shown.
Other listsQuastel Midgen LLP Presentation International Political Economy Research Group Hitachi Cambridge Laboratory
Other talksPLACE Book Launch Sex Education and Faith Communities in the UK: Challenges and Opportunities The influence of the Amundsen-Bellingshausen Seas Low on the climate of West Antarctica and its representation in coupled climate model simulations Linear-scaling time-dependent density-functional theory in the linear-response formalism: An implementation in the ONETEP code TBD & Rab8, a regulator of synapse growth in Frontotemporal Dementia? ‘Intercultural citizenship’ – a purpose for foreign language education?