The Symposium on Compositional Structures is a series of interdisciplinary meetings aiming to support the growing community of researchers interested in the phenomenon of compositionality, from both applied and abstract perspectives, and in particular where category theory serves as a unifying common language. We welcome submissions from researchers across computer science, mathematics, physics, philosophy, and beyond, with the aim of fostering friendly discussion, disseminating new ideas, and spreading knowledge between fields. Submission is encouraged for both mature research and work in progress, and by both established academics and junior researchers, including students.

Submission is easy, with no format requirements or page restrictions. The meeting does not have proceedings, so work can be submitted even if it has been submitted or published elsewhere. You could submit work-in-progress, or a recently completed paper, or even a PhD or Masters thesis.

While no list of topics could be exhaustive, SYCO welcomes submissions with a compositional focus related to any of the following areas, in particular from the perspective of category theory:

This new series aims to bring together the communities behind many previous successful events which have taken place over the last decade, including Categories, Logic and Physics, Categories, Logic and Physics (Scotland), Higher-Dimensional Rewriting and Applications, String Diagrams in Computation, Logic and Physics, Applied Category Theory, Simons Workshop on Compositionality, Yorkshire and Midlands Category Theory Seminar, and the Peripatetic Seminar in Sheaves and Logic.

This event follows SYCO 1 in Birmingham, SYCO 2 in Strathclyde, SYCO 3 in Oxford, SYCO 4 in California, SYCO 5 in Birmingham, SYCO 6 in Leicester, SYCO 8 in Tallinn, SYCO 9 in Como, SYCO 10 in Edinburgh, and SYCO 11 in Palaiseau.

For those interested in extending their visit to the Midlands, we take place just after the Midlands Graduate School 2024 in Leicester on 08-12 April.

Invited speakers

Miriam Backens
INRIA Nancy
Sean Moss
University of Birmingham

Important dates

All deadlines are 23:59 anywhere-on-earth on the given dates.

The important dates can be found in the SYCO 12 calendar.

In-person and online participation

While the SYCO experience is best enjoyed in-person, all talks will be livestreamed for virtual participants. However, speakers are expected to present their contribution in person.

Registration

Registration for in-person attendence has now closed. If you would like to participate virtually, you can still register using the SYCO 12 registration form.

Accepted talks

Schedule

The author marked with an asterisk * will be presenting the talk. All times are in British Summer Time (UTC+1).

Monday 15 April

10:30-11:00
REGISTRATION
Chair: George Kaye
11:00-12:00
Miriam Backens*
Flow-preserving rewriting in the ZX-calculus
The ZX-calculus is a graphical formalism for reasoning about quantum computations whose diagrams form a PROP. It is more intuitive and 'flexible' than traditional formalisms for expressing quantum computations, which makes it useful for applications such as the optimisation of computations. Yet this flexibility is also a disadvantage: turning a general ZX-diagram into a form that can be implemented on a physical quantum computer is computationally hard. Fortunately there is a solution: ZX-diagrams satisfying a property called 'Pauli flow' (or one of a several related properties) can be efficiently transformed so they are implementable.

In this talk I will introduce the ZX-calculus as well as the flow properties, and discuss flow-preserving rewriting and some of its applications.
12:00-12:30
Alexei Lisitsa*, Andrew Fish
Automated Reasoning for Tangles with Quantum Verification Applications
We demonstrate utility of generic automated reasoning (AR) methods in the computational topology domain, evidencing the benefit of the use of existing AR machinery within the domain on the one hand, whilst providing a pathway into a rich playground with potential to drive future AR requirements. We also contribute towards quantum software verification, via a recent proposal to use tangles as a representation of a certain class of quantum programs. The general methodology is to transform tasks of equivalence of topological objects (tangles) into equivalence of algebraic objects (pointed quandles) and those in turn translate into AR tasks. To enhance trust in automated checks, this can be followed by interpretation of AR outputs as human-readable output, either in symbolic algebraic form suitable for domain experts or ideally in visual topological form, potentially suitable for all. We provide formalisation via an appropriate class of labelled tangles (suitable for Quantum Verification) with associated algebraic invariants (pointed involutory quandles) and translate equivalence checking of these invariants to equational reasoning tasks that are realised by Prover 9 and Prover X. Furthermore, subsequent to automated proof creation for quantum verification (QV) examples, we demonstrate manual extraction of visual proof rules and visual equivalence, utilising proof graphs produced by Prover X as a bridging step, progressing towards progressing towards the automation of human-readable visual proofs.
12:30-13:30
LUNCH
Chair: Paul Taylor
13:30-14:00
Flavien Breuvart, Quan Long*, Vladimir Zamdzhiev
On the Centre of Strong Graded Monads
We introduce the notion of “centre” for pomonoid-graded strong monads which generalizes some previous work that describes the centre of (not graded) strong monads. We show that, whenever the centre exists, this determines a pomonoid-graded commutative submonad of the original one. We also discuss how this relates to duoidally-graded strong monads.
14:00-14:30
Aloïs Rosset*, Maaike Zwart, Helle Hvid Hansen, Jörg Endrullis
Correspondence between Composite Theories and Distributive Laws
Composite theories are the algebraic equivalent of distributive laws. In this paper, we delve into the details of this correspondence and concretely show how to construct a composite theory from a distributive law and vice versa. Using term rewriting methods, we also describe when a minimal set of equations axiomatises the composite theory.
14:30-15:00
Adrián Doña Mateo*
Pushing monads forward
Codensity monads are often thought of as the monad induced by a functor and its left adjoint, even when the latter does not exist. The same idea can be applied to the situation of pushing a monad forward along an adjunction. Explicitly, if \(\mathbf{T}\) is a monad on \(\mathcal{C}\) and \(G \colon \mathcal{C} \to \mathcal{D}\) is right adjoint to \(F\), then \(G\mathbf{T}F\) is a monad on \(\mathcal{D}\), which we denote \(G_\ast\mathbf{T}\). Even when \(G\) is not a right adjoint, we can define \(G_\ast\mathbf{T}\) subject to the existence of a right Kan extension. In this note, we study the properties of this construction, which we call the pushforward of monads, and see a few examples. In particular, we examine the pushforwards of several monads from the category of finite sets to \(\mathbf{Set}\). Lastly, we find that the category of algebras for the codensity monad of the inclusion of \(\mathbf{Field}\) into \(\mathbf{Ring}\) is the free (small) product completion of \(\mathbf{Field}\). This turns out to also be monadic over \(\mathbf{Set}\).
15:00-15:30
BREAK
Chair: Paul Blain Levy
15:30-16:00
David Forsman*
Monoidal Meta-Theorem
Some proofs of equations in (cartesian/symmetric) monoidal categories reduce to proving them in the cartesian monoidal category of sets. In the setting of cartesian monoidal categories, this is very well known. As a corollary, the Eckmann-Hilton argument generalizes from sets to all symmetric monoidal categories. We define the theories of multi-sorted universal algebra that can have interpretations in all monoidal, symmetric monoidal and cartesian monoidal categories, respectively. For these theories, we construct sound syntactic deduction systems, which are complete in the cartesian monoidal category of sets. This yields the meta-theorem:

(Monoidal Meta-Theorem)

Let C be a (cartesian/symmetric) monoidal category and let \(E \cup \phi\) be a (cartesian/symmetric) monoidal theory of universal algebra. Then

\(E \vDash \phi\) in \(\mathbf{Set}\) implies that \(E \vDash \phi\) in \(C\)

This meta-theorem makes a modest connection from algebraic structures in \(\mathbf{Set}\) to monoidally enriched algebraic structures.
16:00-16:30
Aziz Kharoof*, Cihan Okay
Homotopical characterization of strong contextuality
Simplicial distributions introduced in the paper “Simplicial quantum contextuality” provide topological and categorical approaches to the study of contextuality for collections of probability distributions. Strong contextuality is a special case of contextuality that help to find contextual vertices and there are models coming from quantum mechanics which are strongly contextual. We give a novel homotopical characterization of strongly contextual simplicial distributions with binary outcomes, specifically those defined on the cone of a 1-dimensional space. To prove this result, we associate to a simplicial distribution a category whose morphisms correspond to conditional probability distributions. The composition in this category is induced by the 0-order composition of the compository (in the sense of the paper “Compositories and gleaves”) that we get by applying the distribution monad on the nerve of a small category. The result shows that the strong contextuality depends only on loops in the associated category.
16:30-17:00
Joshua Wrigley*
A topos-theoretic framework for reconstruction theorems in model theory
A classical result in model theory [1] asserts that an atomic/countably categorical theory can be reconstructed, up to bi-interpretability, from the topological automorphism group of its unique countable model. Recent work by Ben Yaacov has shown that the atomicity/countable categoricity assumption can be dropped if, instead of a topological group, one uses a topological groupoid. However, the groupoid considered in [2] is not a groupoid of models for the theory.

In this presentation, we will demonstrate how the theorem of Ahlbrandt and Ziegler can be recovered and generalised by topos-theoretic means, using the representation of classifying toposes by topological groupoids (as in [3] and [4]). We will show that two theories \(T_1\), \(T_2\) with representing groupoids of models are Morita equivalent (which is equivalent to bi-interpretability in the classical context, see [5]) if and only if the representing groupoids \(\mathcal{X}\), \(\mathcal{Y}\) admit a cospan

\(\mathcal{X} \to \mathcal{W} \leftarrow \mathcal{Y}\)

of weak equivalences. The work is based on the author’s PhD thesis [6].

[1] G. Ahlbrandt and M. Ziegler, “Quasi finitely axiomatizable totally categorical theories,” Annals of Pure and Applied Logic, vol. 30, no. 1, pp. 63–82, 1986.

[2] I. Ben Yaacov, “Reconstruction of non-ℵ0-categorical theories,” The Journal of Symbolic Logic, vol. 87, no. 1, pp. 159–187, 2022.

[3] C. Butz and I. Moerdijk, “Representing topoi by topological groupoids,” Journal of Pure and Applied Algebra, vol. 130, no. 3, pp. 223–235, 1998.

[4] H. Forssell, “Topological representation of geometric theories,” Mathematical Logic Quarterly vol. 58, no. 6, pp. 380–393, 2012.

[5] P.A. McEldowney, “On Morita equivalence and interpretability”, Review of Symbolic Logic, vol. 13, no. 2, pp. 388–393 (2012).

[6] J. Wrigley, “Doctrinal and groupoidal representations of classifying topoi,” Ph.D. dissertation, University of Insubria, 2024. Available at: https://jlwrigley.github.io/thesis/thesis_wrigley.pdf
18:00-22:00
EVENING SOCIAL AND MEAL AT CHERRY REDS

Tuesday 16 April

Chair: Sam Speight
09:30-10:30
Sean Moss*
The Markov category of a random graph
In graph theory and combinatorics, very large graphs are sometimes studied and distinguished by randomly sampling induced finite subgraphs. In this theory, idealized large graphs are represented by objects called 'graphons'. Tests based on sampling induced finite subgraphs can be written in a simple programming language or, put another way, they form a Markov category. I will explain how Markov categories with suitable structure - including support for the graph programming interface - each give rise to a graphon; and, conversely, every graphon arises this way. This gives a new characterization of graphons in terms of Markov categories. This talk is based on joint work published at POPL 2024.
10:30-11:00
Grégoire Sergeant-Perthuis*
Compositional statistical mechanics, entropy and variational inference
In this document, we aim to gather various results related to a compositional/categorical approach to rigorous Statistical Mechanics. Rigorous Statistical Mechanics is centered on the mathematical study of statistical systems. Central concepts in this field have a natural expression in terms of diagrams in a category that couples measurable maps and Markov kernels. We showed that statistical systems are particular representations of partially ordered sets (posets), that we call -specifications, and expressed their phases, i.e., Gibbs measures, as invariants of these representations. It opens the way to the use of homological algebra to compute phases of statistical systems. Two central results of rigorous Statistical Mechanics are, firstly, the characterization of extreme Gibbs measure as it relates to the zero–one law for extreme Gibbs measures, and, secondly, their variational principle which states that for translation invariant Hamiltonians, Gibbs measures are the minima of the Gibbs free energy. We showed how the characterization of extreme Gibbs measures extends to -specifications; we proposed an Entropy functional for -specifications and gave a message-passing algorithm, that generalized the belief propagation algorithm of graphical models (see O. Peltre's SYCO 8 talk), to minimize variations free energy.
11:00-11:30
BREAK
Chair: Miriam Backens
11:30-12:00
Filippo Bonchi, Alessandro Di Giorgio*, Nathan Haydon, Pawel Sobocinski
Diagrammatic Algebra of First Order Logic
We introduce the calculus of neo-Peircean relations, a string diagrammatic extension of the calculus of binary relations that has the same expressivity as first order logic and comes with a complete axiomatisation. The axioms are obtained by combining two well known categorical structures: cartesian and linear bicategories.
12:00-12:30
Pablo Donato*
The Flower Calculus
We introduce the flower calculus, a deep inference proof system for intuitionistic first-order logic inspired by Peirce’s existential graphs. It works as a rewriting system over inductive objects called “flowers”, that enjoy both a graphical interpretation as topological diagrams, and a textual presentation as nested sequents akin to coherent formulas. Importantly, the calculus dispenses completely with the traditional notion of symbolic connective, operating solely on nested flowers containing atomic predicates. We prove both the soundness of the full calculus and the completeness of an analytic fragment with respect to Kripke semantics. This provides to our knowledge the first analyticity result for a proof system based on existential graphs, adapting semantic cut-elimination techniques to a deep inference setting. Furthermore, the kernel of rules targetted by completeness is fully invertible, a desirable property for both automated and interactive proof search.
12:30-13:00
Nathan Corbyn, Lukas Heidemann, Nick Hu*, Chiara Sarti, Calin Tataru, Jamie Vicary
homotopy.io: a proof assistant for finitely-presented globular n-categories
We present the proof assistant homotopy.io for working with finitely-presented semistrict higher categories. The tool runs in the browser with a point-and-click interface, allowing direct manipulation of proof objects via a graphical representation. We describe the user interface and explain how the tool can be used in practice. We also describe the essential subsystems of the tool, including collapse, contraction, expansion, typechecking, and layout, as well as key implementation details including data structure encoding, memoisation, and rendering. These technical innovations have been essential for achieving good performance in a resource-constrained setting.
13:00-14:00
LUNCH
Chair: Todd Ambridge
14:00-14:30
Tanguy Massacrier*, Philippe Malbos, Georg Struth
Single-set cubical categories and their formalisation with a proof assistant
We introduce a single-set axiomatisation of cubical \(\omega\)-categories, including connections and inverses. We justify these axioms by establishing a series of equivalences between the category of single-set cubical \(\omega\)-categories, and their variants with connections and inverses, and the corresponding cubical \(\omega\)-categories. We also report on the formalisation of cubical \(\omega\)-categories with the Isabelle/HOL proof assistant, which has been instrumental in finding the single-set axioms.
14:30-15:00
Bruno Gavranović*, Paul Lessard, Andrew Joseph Dudzik, Tamara von Glehn, João Guilherme Madeira Araújo, Petar Veličković
Categorical Deep Learning: An Algebraic Theory of Architectures
We present our position on the elusive quest for a general-purpose framework for specifying and studying deep learning architectures. Our opinion is that the key attempts made so far lack a coherent bridge between specifying constraints which models must satisfy and specifying their implementations. Focusing on building a such a bridge, we propose to apply category theory— precisely, the universal algebra of monads valued in a 2-category of parametric maps—as a single theory elegantly subsuming both of these flavours of neural network design. To defend our position, we show how this theory recovers constraints induced by geometric deep learning, as well as implementations of many architectures drawn from the diverse landscape of neural networks, such as RNNs. We also illustrate how the theory naturally encodes many standard constructs in computer science and automata theory.
15:00-15:30
Paul B Levy*
Game-enriched categories
Currently, game models of programming languages are presented as mere categories. I suggest that, where possible, we should instead present them as game-enriched categories. A potential benefit is that this would make it easier to vary the notion of strategy.

(Presented at the GALOP 2024 workshop.)
15:30
END

Local information

Talks will take place in the Old Gym in room LG10, which can be found on the lower ground floor, down the stairs from the entrance.

Lunches are provided and will take place in the atrium of the School of Computer Science, which is a short walk up the hill from the Old Gym. Coffee breaks will take place in the seminar room.

All the relevant locations can be found on the SYCO 12 map.

See full screen

Transport

Train

The main railway station in Birmingham is Birmingham New Street, which receives direct services from all over the country including London, Manchester, Oxford, Cambridge, Bristol, Edinburgh and Glasgow. Services from London to Birmingham New Street depart from London Euston, which is a ten minute walk from London St Pancras, the Eurostar terminus. An alternative route from London that some find more pleasant is to travel from London Marylebone to Birmingham Moor Street, which is a five minute walk from New Street.

The university has its own railway station, fittingly titled University. There is a regular service from Birmingham New Street to University, usually departing from platform 12B: look for trains going to Redditch, Bromsgrove, Longbridge, Worcester, Hereford, or Cardiff Central. A word of warning to those who have visited University station before: the station has a new building now and the original entrance/exit is closed for refurbishment, so don't head down to the end of the platform when alighting from the train!

It is often no added charge to extend a ticket to Birmingham New Street to University. On tickets that are not Advance Singles it is fine to 'break your journey' so you are permitted to alight at Birmingham New Street and get back on a train to University later in the day, or vice versa.

Journeys can be planned using the National Rail website. Tickets can be purchased from machines or ticket offices at railway stations, or from train operator websites such as the West Midlands Railway website without paying a booking fee. Purchasing tickets from sites such as Trainline should be avoided as the fares are exactly the same price and a booking fee is added to the cost. Trains can be tracked using Realtime Trains.

Bus

The University is well-served by bus: the National Express West Midlands services X21, X22, 61, and 63 call nearby and stop outside Birmingham New Street at stop NS3.

The easiest way to pay for National Express West Midlands buses in Birmingham is to simply tap the card reader by the driver with a contactless bank card when you get on; you do not need to tap off. A single journey is £2 and there is a daily cap of £4.50. Individual tickets can be bought on the bus with contactless card or cash in exact change: ask the driver for a single (£2 for any journey) or a Daysaver (£4.50 for travel all day in the West Midlands). If travelling in a group, a Group Daysaver costs £8 and allows up to five people to travel together on one ticket.

It is possible to follow buses on a map in (relative) real-time using bustimes.org. Google Maps also shows real-time information.

Air

The nearest airport to Birmingham is Birmingham Airport, which has its own railway station called Birmingham International. which is a ten minute direct train ride to Birmingham New Street. There is also a direct rail service between Birmingham and London Stansted Airport which takes about three hours. for the other London airports (Heathrow, Gatwick, Luton, City) it is probably best to travel into London and then onwards to Birmingham, which will take about two hours. Manchester Airport, Liverpool John Lennon Airport, and Bristol Airport are also about two hours to Birmingham.

Accommodation

There are plenty of hotels in the centre of Birmingham; we recommend getting one near Birmingham New Street station. There are also many AirBnB places available, especially near Birmingham New Street or Five Ways railway stations, the latter of which is also on the line to University station.

Social activities

Pub social

On the evening before the workshop, Sunday 14 April from 17:00, we will gather at The British Oak, a pub in Stirchley. The British Oak is a short walk from Bournville railway station, which is a fifteen minute train from New Street. Alternatively, the 45 and 47 buses stop outside the pub and can be caught from stop NS4 outside New Street station.

We have booked out the Penn Room, which is on the right side of the pub. From the main entrance, turn left and walk clockwise all the way around the pub. There is also another entrance on the the right side of the building that leads right past the room.

Food can be purchased at the British Oak from burger connoisseurs Original Patty Men; they are open until 19:00 or until their stocks run out, so hopefully they will still be going when we get therer.

Evening meal

On the evening of Monday 15 April from 18:00, we will have a buffet dinner at independent cafe-bar Cherry Reds, at participants' own cost (£14 each). We will be having a selection of the 'Big Red Buffet' and 'All Vegan' platters, the details of which can be found on the Cherry Reds buffet menu. We have booked out the Bosta Room, which can be found by going upstairs and turning left at the top.

A three storey redbrick corner building with 'Cherry Reds cafe bar' written on the front A room with assorted tables and chairs; a long wavy sofa seat is on the left and fairy lights hang from the ceiling.

Cherry Reds is less than a five minute walk from Birmingham New Street railway station. If you are arriving by train, it can be quicker to walk to the far end of the 'B' end of the platform, go up the very last staircase and turn left. Once you exit the station onto Hill Street, cross the road and continue straight ahead; Cherry Reds will be on your left.

Attendees

Attendees marked with an asterisk * will attend physically.

Local organizers

Todd Ambridge
University of Birmingham
George Kaye
University of Birmingham

Programme committee

Todd Ambridge
University of Birmingham
Thibaut Benjamin
University of Cambridge
Olivia Caramello
University of Insubria
Ross Duncan
University of Strathclyde
Chris Heunen
University of Edinburgh
Dominic Horsman
Dominic Horsman
University of Grenoble
George Kaye
University of Birmingham
Aleks Kissinger
University of Oxford
Jean-Simon Lemay
Macquarie University
Paul Levy
University of Birmingham
Ioannis Markakis
University of Cambridge
Samuel Mimram
École Polytechnique
Paige North
Utrecht University
Simona Paoli
University of Aberdeen
Mehrnoosh Sadzradeh
University College London
Pawel Sobocinski
Tallinn University of Technology
Jamie Vicary
University of Cambridge

Steering committee

The symposium is managed by the following people. If you have a general question about SYCO, or if you want to propose to host a future iteration, please get in touch with a member of the steering committee.

Ross Duncan
University of Strathclyde
Chris Heunen
University of Edinburgh
Dominic Horsman
Dominic Horsman
University of Grenoble
Aleks Kissinger
University of Oxford
Samuel Mimram
École Polytechnique
Simona Paoli
University of Aberdeen
Mehrnoosh Sadzradeh
University College London
Pawel Sobocinski
Tallinn University of Technology
Jamie Vicary
University of Cambridge

Sponsorship

Thanks to Dan Ghica for providing funding from his EPSRC grant, and to Martin Escardo and Sonia Marin for providing funding from the Theory Group's budget. Without their contributions this edition of SYCO would not have been able to go ahead!