Structured Decompositions: recursive data and recursive algorithms

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

• Benjamin Bumpus, Glasgow
• Thursday 08 December 2022, 15:00-16:00
• LTC.

If you have a question about this talk, please contact Johannes Carmesin.

What is recursive structure? And how can we exploit it algorithmically?  In this talk I will give as general an answer as I can to these questions by calling upon the new notion of structured decompositions. This is a category-theoretic formalism that Jade Master, Zoltan Kocsis and I recently introduced which yields a vast generalisation of tree-width to arbitrary categories. I will explain — assuming no prior knowledge at all of category theory — how to make use of structured decompositions for three purposes: (1) defining new tree-width-like invariants, (2) relating these decompositions to each-other via functors and (3) how one might go about proving algorithmic meta-theorems using the language of category theory.  This is ongoing, multidisciplinary work. As such it requires lots people with different types of expertise, so you should consider this talk is an invitation to get involved! 

This talk is part of the Combinatorics and Probability Seminar series.

This talk is included in these lists:

• Combinatorics and Probability Seminar
• LTC
• School of Mathematics Events

Note that ex-directory lists are not shown.