In an earlier post, we showed how to construct epidemiological models, including part of the COEXIST model of COVID-19, by composing structured cospans of Petri nets. We have since talked about this project at the UCR Categories Seminar. The slides are now online and the video is below:

The talk mostly followed the blog post, but with one significant departure: we shifted from composing structured cospans in a categorical style to composing structured multicospans in an operadic style, using undirected wiring diagrams. That change in perspective and the rationale behind it will be the topic of this post.

Structured cospans, or their isomorphism classes, are usually thought to form a symmetric monoidal double category or a hypergraph category. This formulation implies two things. First, structured cospans, like the morphisms in any category, are *directed*: one leg of the cospan is designated as input (domain) and the other as output (codomain). Second, the algebraic structure possessed by structured cospans is expressed in *biased* style via primitive operations of fixed arity, such as the binary operations of composition (\(\circ\)) and monoidal product (\(\otimes\)). This is mathematically appealing, especially if you are a category theorist, because it expresses the structure in a parsimonious way and highlights family relationships with other categorical structures.

But the parsimony that is so convenient in mathematics is inconvenient for computing. In order to construct a large structured cospan out of smaller ones, the construction must be decomposed into primitive operations, such as compositions, products, swaps, copies, and merges. The decomposition can be done manually, which is tedious and error-prone. It can also be done automatically, starting from a directed wiring diagram, which is algorithmically complicated and incurs nonnegligible runtime cost.^{[1]} In addition, the directedness of morphisms in a category here is artificial: structured cospans do not meaningfully have inputs or outputs, since the legs of the cospan can always be swapped. Experience shows that this mismatch causes confusion when explaining open Petri nets to the uninitiated.

Both problems are solved by viewing structured cospans, or rather structured *multi*cospans, as an algebra of the operad of undirected wiring diagrams (Spivak 2013). Let us now explain the jargon in this sentence.

A structured multicospan is like a structured cospan except that it may have any number of legs. Formally, given a functor \(L: \mathsf{A} \to \mathsf{X}\), a **structured multicospan** is a diagram in \(\mathsf{X}\) of form

where the object \(x \in \mathsf{X}\) is the system and the objects \(a_1,\dots,a_n \in \mathsf{A}\) are "ports" defining the interface of the system.

Undirected wiring diagrams represent compositions in a hypergraph category in an unbiased fashion. As a result, they are a natural syntax in many applications. In the previous post, for instance, undirected wiring diagrams were syntax for conjunctive queries on a relational database. In this post, they are syntax for composites of structured multicospans, which are colimits in \(\mathsf{X}\). For example, the wiring diagram

represents a composite of three structured multicospans \(x\), \(y\), and \(z\), each with three legs. It translates into the diagram in \(\mathsf{X}\)

whose colimit is the composite of \(x\), \(y\), and \(z\), a structured multicospan with no legs. In technical language, undirected wiring diagrams form a typed *operad*, whose types are the objects of \(\mathsf{A}\), and isomorphism classes of structured multicospans are an *algebra* of this operad.

To see how all this is expressed in code and applied to build complex Petri net models, you can watch the talk linked above or read the COEXIST model example in the documentation for AlgebraicPetri.jl.

[1] | In the original post, we do the latter using the `to_hom_expr` function in Catlab. This detail was elided in the interest of clarity; we will now bypass it entirely. |

David Spivak, 2013. The operad of wiring diagrams: formalizing a graphical language for databases, recursion, and plug-and-play circuits. arXiv:1305.0297

© Micah Halter and Evan Patterson. Last modified: January 25, 2021. This site is powered by Netlify, Franklin.jl, and the Julia programming language.