Circuits, Bond Graphs, and Signal-Flow Diagrams

 

My student Brandon Coya finished his thesis, and successfully defended it last Tuesday!

• Brandon Coya, Circuits, Bond Graphs, and Signal-Flow Diagrams: A Categorical Perspective, Ph.D. thesis, U. C. Riverside, 2018.

It’s about networks in engineering. He uses category theory to study the diagrams engineers like to draw, and functors to understand how these diagrams are interpreted.

His thesis raises some really interesting pure mathematical questions about the category of corelations and a ‘weak bimonoid’ that can be found in this category. Weak bimonoids were invented by Pastro and Street in their study of ‘quantum categories’, a generalization of quantum groups. So, it’s fascinating to see a weak bimonoid that plays an important role in electrical engineering!

However, in what follows I’ll stick to less fancy stuff: I’ll just explain the basic idea of Brandon’s thesis, say a bit about circuits and ‘bond graphs’, and outline his main results. What follows is heavily based on the introduction of his thesis, but I’ve baezified it a little.

The basic idea

People, and especially scientists and engineers, are naturally inclined to draw diagrams and pictures when they want to better understand a problem. One example is when Feynman introduced his famous diagrams in 1949; particle physicists have been using them ever since. But some other diagrams introduced by engineers are far more important to the functioning of the modern world and its technology. It’s outrageous, but sociologically understandable, that mathematicians have figured out more about Feynman diagrams than these other kinds: circuit diagrams, bond graphs and signal-flow diagrams. This is the problem Brandon aims to fix.

I’ve been unable to track down the early history of circuit diagrams, so if you know about that please tell me! But in the 1940s, Harry Olson pointed out analogies in electrical, mechanical, thermodynamic, hydraulic, and chemical systems, which allowed circuit diagrams to be applied to a wide variety of fields. On April 24, 1959, Henry Paynter woke up and invented the diagrammatic language of bond graphs to study generalized versions of voltage and current, called ‘effort’ and ‘flow,’ which are implicit in the analogies found by Olson. Bond graphs are now widely used in engineering. On the other hand, control theorists use diagrams of a different kind, called ‘signal-flow diagrams’, to study linear open dynamical systems.

Although category theory predates some of these diagrams, it was not until the 1980s that Joyal and Street showed string digrams can be used to reason about morphisms in any symmetric monoidal category. This motivates Brandon’s first goal: viewing electrical circuits, signal-flow diagrams, and bond graphs as string diagrams for morphisms in symmetric monoidal categories.

This lets us study networks from a compositional perspective. That is, we can study a big network by describing how it is composed of smaller pieces. Treating networks as morphisms in a symmetric monoidal category lets us build larger ones from smaller ones by composing and tensoring them: this makes the compositional perspective into precise mathematics. To study a network in this way we must first define a notion of ‘input’ and ‘output’ for the network diagram. Then gluing diagrams together, so long as the outputs of one match the inputs of the other, defines the composition for a category.

Network diagrams are typically assigned data, such as the potential and current associated to a wire in an electrical circuit. Since the relation between the data tells us how a network behaves, we call this relation the ‘behavior’ of a network. The way in which we assign behavior to a network comes from first treating a network as a ‘black box’, which is a system with inputs and outputs whose internal mechanisms are unknown or ignored. A simple example is the lock on a doorknob: one can insert a key and try to turn it; it either opens the door or not, and it fulfills this function without us needing to know its inner workings. We can treat a system as a black box through the process called ‘black-boxing’, which forgets its inner workings and records only the relation it imposes between its inputs and outputs.

Since systems with inputs and outputs can be seen as morphisms in a category we expect black-boxing to be a functor out of a category of this sort. Assigning each diagram its behavior in a functorial way is formalized by functorial semantics, first introduced in Lawvere’s thesis in 1963. This consists of using categories with specific extra structure as ‘theories’ whose ‘models’ are structure-preserving functors into other such categories. We then think of the diagrams as a syntax, while the behaviors are the semantics. Thus black-boxing is actually an example of functorial semantics. This leads us to another goal: to study the functorial semantics, i.e. black-boxing functors, for electrical circuits, signal-flow diagrams, and bond graphs.

Brendan Fong and I began this type of work by showing how to describe circuits made of wires, resistors, capacitors, and inductors as morphisms in a category using ‘decorated cospans’. Jason Erbele and I, and separately Bonchi, Sobociński and Zanasi, studied signal flow diagrams as morphisms in a category. In other work Brendan Fong, Blake Pollard and I looked at Markov processes, while Blake and I studied chemical reaction networks using decorated cospans. In all of these cases, we also studied the functorial semantics of these diagram languages.

Brandon’s main tool is the framework of ‘props’, also called ‘PROPs’, introduced by Mac Lane in 1965. The acronym stands for “products and permutations”, and these operations roughly describe what a prop can do. More precisely, a prop is a strict symmetric monoidal category equipped with a distinguished object such that every object is a tensor power Props arise because very often we think of a network as going between some set of input nodes and some set of output nodes, where the nodes are indistinguishable from each other. Thus we typically think of a network as simply having some natural number as an input and some natural number as an output, so that the network is actually a morphism in a prop.

Circuits and bond graphs

Now let’s take a quick tour of circuits and bond graphs. Much more detail can be found in Brandon’s thesis, but this may help you know what to picture when you hear terminology from electrical engineering.

Here is an electrical circuit made of only perfectly conductive wires:

This is just a graph, consisting of a set of nodes, a set of edges, and maps sending each edge to its source and target node. We refer to the edges as perfectly conductive wires and say that wires go between nodes. Then associated to each perfectly conductive wire in an electrical circuit is a pair of real numbers called ‘potential’, and ‘current’,

Typically each node gets a potential, but in the above case the potential at either end of a wire would be the same so we may as well associate the potential to the wire. Current and potential in circuits like these obey two laws due to Kirchoff. First, at any node, the sum of currents flowing into that node is equal to the sum of currents flowing out of that node. The other law states that any connected wires must have the same potential.

We say that the above circuit is closed as opposed to being open because it does not have any inputs or outputs. In order to talk about open circuits and thereby bring the ‘compositional perspective’ into play we need a notion for inputs and outputs of a circuit. We do this using two maps and that specifiy the inputs and outputs of a circuit. Here is an example:

We call the sets and the disjoint union the inputs, outputs, and terminals of the circuit, respectively. To each terminal we associate a potential and current. In total this gives a space of allowed potentials and currents on the terminals and we call this space the ‘behavior’ of the circuit. Since we do this association without knowing the potentials and currents inside the rest of the circuit we call this process ‘black-boxing’ the circuit. This process hides the internal workings of the circuit and just tells us the relation between inputs and outputs. In fact this association is functorial, but to understand the functoriality first requires that we say how to compose these kinds of circuits. We save this for later.

There are also electrical circuits that have ‘components’ such as resistors, inductors, voltage sources, and current sources. These are graphs as above, but with edges now labelled by elements in some set L. Here is one for example:

We call this an L-circuit. We may also black-box an L-circuit to get a space of allowed potentials and currents, i.e. the behavior of the L-circuit, and this process is functorial as well. The components in a circuit determine the possible potential and current pairs because they impose additional relationships. For example, a resistor between two nodes has a resistance and is drawn as:

In an L-circuit this would be an edge labelled by some positive real number For a resistor like this Kirchhoff’s current law says and Ohm’s Law says This tells us how to construct the black-boxing functor that extracts the right behavior.

Engineers often work with wires that come in pairs where the current on one wire is the negative of the current on the other wire. In such a case engineers care about the difference in potential more than each individual potential. For such pairs of perfectly conductive wires:

we call the ‘voltage’ and the ‘current’. Note the word current is used for two different, yet related concepts. We call a pair of wires like this a ‘bond’ and a pair of nodes like this a ‘port’. To summarize we say that bonds go between ports, and in a ‘bond graph’ we draw a bond as follows:

Note that engineers do not explicitly draw ports at the ends of bonds; we follow this notation and simply draw a bond as a thickened edge. Engineers who work with bond graphs often use the terms ‘effort’ and ‘flow’ instead of voltage and current. Thus a bond between two ports in a bond graph is drawn equipped with an effort and flow, rather than a voltage and current, as follows:

A bond graph consists of bonds connected together using ‘1-junctions’ and ‘0-junctions’. These two types of junctions impose equations between the efforts and flows on the attached bonds. The flows on bonds connected together with a 1-junction are all equal, while the efforts sum to zero, after sprinkling in some signs depending on how we orient the bonds. For 0-junctions it works the other way: the efforts are all equal while the flows sum to zero! The duality here is well-known to engineers but perhaps less so to mathematicians. This is one topic Brandon’s thesis explores.

Brandon explains bond graphs in more detail in Chapter 5 of his thesis, but here is an example:

The arrow at the end of a bond indicates which direction of current flow counts as positive, while the bar is called the ‘causal stroke’. These are unnecessary for Brandon’s work, so he adopts a simplified notation without the arrow or bar. In engineering it’s also important to attach general circuit components, but Brandon doesn’t consider these.

Outline

In Chapter 2 of his thesis, Brandon provides the necessary background for studying four categories as props:

• the category of finite sets and spans:

• the category of finite sets and relations:

• the category of finite sets and cospans:

• the category of finite sets and corelations:

In particular, and are crucial to the study of networks.

In Corollary 2.3.4 he notes that any prop has a presentation in terms of generators and equations. Then he recalls the known presentations for and Proposition 2.3.7 lets us build props as quotients of other props.

He begins Chapter 3 by showing that is ‘the prop for extraspecial commutative Frobenius monoids’, based on a paper he wrote with Brendan Fong. This result also gives a presentation for

Then he defines an “L-circuit” as a graph with specified inputs and outputs, together with a labelling set for the edges of the graph. L-circuits are morphisms in the prop In Proposition 3.2.8 he uses a result of Rosebrugh, Sabadini and Walters to show that can be viewed as the coproduct of and the free prop on the set L of labels.

Brandon then defines to be the prop where L consists of a single element. This example is important, because can be seen as the category whose morphisms are circuits made of only perfectly conductive wires! From any morphism in he extracts a cospan of finite sets and then turns the cospan into a corelation. These two processes are functorial, so he gets a method for sending a circuit made of only perfectly conductive wires to a corelation:

There is also a functor

where is the category whose objects are finite dimensional vector spaces and whose morphisms are linear relations, that is, linear subspaces By composing with the above functors and he associates a linear relation to any circuit made of perfectly conductive wires. On the other hand he gets a subspace for any such circuit by first assigning potential and current to each terminal, and then subjecting these variables to the appropriate physical laws.

It turns out that these two ways of assigning a subspace to a morphism in are the same. So, he calls the linear relation associated to a circuit using the composite the “behavior” of the circuit and defines the “black-boxing” functor

to be the composite of these:

Note that the underlying corelation of a circuit made of perfectly conductive wires completely determines the behavior of the circuit via the functor

In Chapter 4 he reinterprets the black-boxing functor as a morphism of props. He does this by introducing the category whose objects are “symplectic” vector spaces and whose morphisms are “Lagrangian” relations. In Proposition 4.1.6 he proves that the functor actually picks out a Lagrangian relation for any corelation and thus determines a morphism of props. So, he redefines to be this morphism

and reinterprets black-boxing as the composite

After doing al this hard work for circuits made of perfectly conductive wires—a warmup exercises that engineers might scoff at—Brandon shows the power of his results by easily extending the black-boxing functor to circuits with arbitrary label sets in Theorem 4.2.1. He applies this result to a prop whose morphisms are circuits made of resistors, inductors, and capacitors. Then he considers a more general and mathematically more natural approach to linear circuits using the prop The morphisms here are open circuits with wires labelled by elements of some chosen field In Theorem 4.2.4 he prove the existence of a morphism of props

that describes the black-boxing of circuits built from arbitrary linear components.

Brandon then picks up where Jason Erbele’s thesis left off, and recalls how control theorists use “signal-flow diagrams” to draw linear relations. These diagrams make up the category which is the free prop generated by the same generators as Similarly he defines the prop as the free prop generated by the same generators as Then there is a strict symmetric monoidal functor giving a commutative square:

Of course, circuits made of perfectly conductive wires are a special case of linear circuits. We can express this fact using another commutative square:

Combining the diagrams so far, Brandon gets a commutative diagram summarizing the relationship between linear circuits, cospans, corelations, and signal-flow diagrams:

Brandon concludes Chapter 4 by extending his work to circuits with voltage and current sources. These types of circuits define affine relations instead of linear relations. The prop framework lets Brandon extend black-boxing to these types of circuits by showing that affine Lagrangian relations are morphisms in a prop This leads to Theorem 4.4.5, which says that for any field and label set L there is a unique morphism of props

extending the other black-boxing functor and sending each element of L to an arbitrarily chosen affine Lagrangian relation between potentials and currents.

In Chapter 5, Brandon studies bond graphs as morphisms in a category. His goal is to define a category whose morphisms are bond graphs, and then assign a space of efforts and flows as behavior to any bond graph using a functor. He also constructs a functor that assigns a space of potentials and currents to any bond graph, which agrees with the way that potential and current relate to effort and flow.

The subtle way he defines comes from two different approaches to studying bond graphs, and the problems inherent in each approach. The first approach leads him to a subcategory of while the second leads him to a subcategory of There isn’t a commutative square relating these four categories, but Brandon obtains a pentagon that commutes up to a natural transformation by inventing a new category :

This category is a way of formalizing Paynter’s idea of bond graphs.

In his first approach, Brandon views a bond graph as an electrical circuit. He takes advantage of his earlier work on circuits and corelations by taking to be the category whose morphisms are circuits made of perfectly conductive wires. In this approach a terminal is the object 1 and a wire is the identity corelation from 1 to 1, while a circuit from m terminals to n terminals is a corelation from m to n.

In this approach Brandon thinks of a port as the object 2, since a port is a pair of nodes. Then he thinks of a bond as a pair of wires and hence the identity corelation from 2 to 2. Lastly, the two junctions are two different ways of connecting ports together, and thus specific corelations from 2m to 2n. It turns out that by following these ideas he can equip the object 2 with two different Frobenius monoid structures, which behave very much like 1-junctions and 0-junctions in bond graphs!

It would be great if the morphisms built from these two Frobenius monoids corresponded perfectly to bond graphs. Unfortunately there are some equations which hold between morphisms made from these Frobenius monoids that do not hold for corresponding bond graphs. So, Brandon defines a category using the morphisms that come from these two Frobenius monoids and moves on to a second attempt at defining

Since bond graphs impose Lagrangian relations between effort and flow, this second approach starts by looking back at The relations associated to a 1-junction make into yet another Frobenius monoid, while the relations associated to a 0-junction make into a different Frobenius monoid. These two Frobenius monoid structures interact to form a bimonoid! Unfortunately, a bimonoid has some equations between morphisms that do not correspond to equations between bond graphs, so this approach also does not result in morphisms that are bond graphs. Nonetheless, Brandon defines a category using the two Frobenius monoid structures

Since it turns out that and have corresponding generators, Brandon defines as a prop that also has corresponding generators, but with only the equations found in both and By defining in this way he automatically gets two functors

and

The functor associates effort and flow to a bond graph, while the functor lets us associate potential and current to a bond graph using the previous work done on Then the Lagrangian subspace relating effort, flow, potential, and current:

defines a natural transformation in the following diagram:

Putting this together with the diagram we saw before, Brandon gets a giant diagram which encompasses the relationships between circuits, signal-flow diagrams, bond graphs, and their behaviors in category theoretic terms:

This diagram is a nice quick road map of his thesis. Of course, you need to understand all the categories in this diagram, all the functors, and also their applications to engineering, to fully appreciate what he has accomplished! But his thesis explains that.

To learn more

Coya’s thesis has lots of references, but if you want to see diagrams at work in actual engineering, here are some good textbooks on bond graphs:

• D. C. Karnopp, D. L. Margolis and R. C. Rosenberg, System Dynamics: A Unified Approach, Wiley, New York, 1990.

• F. T. Brown, Engineering System Dynamics: A Unified Graph-Centered Approach, Taylor and Francis, New York, 2007.

and here’s a good one on signal-flow diagrams:

• B. Friedland, Control System Design: An Introduction to State-Space Methods, S. W. Director (ed.), McGraw–Hill Higher Education, 1985.

Cospans, Wiring Diagrams, and the Behavioral Approach

joint with Brendan Fong

We’re getting ready for the Turin workshop on the
Categorical Foundations of Network Theory. So, we’re trying to get our thoughts in order.

Last time we talked about understanding types of networks as categories of decorated cospans. Earlier, David Spivak told us about understanding networks as algebras of an operad. Both these frameworks work at capturing notions of modularity and interconnection. Are they then related? How?

In this post we want to discuss some similarities between decorated cospan categories and algebras for Spivak’s operad of wiring diagrams. The main idea is that the two approaches are ‘essentially’ equivalent, but that compared to decorated cospans, Spivak’s operad formalism puts greater emphasis on the distinction between the ‘duplication’ and ‘deletion’ morphisms and other morphisms in our category.

The precise details are still to be worked out—jump in and help us!

Operads

We begin with a bit about operads in general. Recall that an operad is similar to a category, except that instead of a set of morphisms from any object to any object you have a set of operations from any finite list of objects to any object If we have an operation we can call the inputs of and call the output of

We can compose operations in an operad. To understand how, it’s easiest to use pictures. We draw an operation in as a little box with wires coming in and one wire coming out:

The input wires should be labelled with the objects and the output wire with the object but I haven’t done this.

We are allowed to compose these operations as follows:

as long as the outputs of the operations match the inputs of the operation The result is a new operation which we call

We demand that there be unary operations serving as identities for composition, and we impose an associative law that makes a composite of composites like this well-defined:

So far this is the definition of a operad without permutations. In a full-fledged permutative operad, we can also permute the inputs of an operation and get a new operation:

which we call if is the the permutation of the inputs. We demand that And finally, we demand that permutations act in a way that is compatible with composition. For example:

Here we see that is equal to some obvious other thing.

Finally, there is a law saying

for some choice of that you can cook up from the permuations in an obvious way. We leave it as an exercise to work out the details. By the way, one well-known book on operads accidentally omits this law, so here’s a rather more lengthy exercise: read this book, see which theorems require this law, and correct their proofs!

Operads are similar to symmetric monoidal categories. The idea is that in a symmetric monoidal category you can just form the tensor product and talk about the set of morphisms Indeed any symmetric monoidal category gives an operad in this way: just define to be If we do this with Set, which is a symmetric monoidal category using the usual cartesian product of sets, we get an operad called

An algebra for an operad is an operad homomorphism We haven’t said what an operad homomorphism is, but you can probably figure it out yourself. The point is this: an algebra for turns the abstract operations in into actual operations on sets!

Finally, we should warn you that operads come in several flavors, and we’ve been talking about ‘typed permutative operads’. ‘Typed’ means that there’s more than one object; ‘permutative’ means that we have the ability to permute the input wires. When people say ‘operad’, they often mean an untyped permutative operad. For that, just specialize down to the case where there’s only one object

You can see a fully precise definition of untyped permutative operads here:

• Operad theory, Wikipedia.

along with the definition of an untyped operad without permutations.

The operad of wiring diagrams

Spivak’s favorite operad is the operad of wiring diagrams. The operad of wiring diagrams is an operad version of constructed in the vein suggested above: the objects are finite sets, and an operation from a list of sets to a set is a cospan

Spivak draws such a thing as a big circle with small circles cut out from the interior:

The outside of the big circle has a set of terminals marked on it, and each small circle has a set of terminals marked on it. Then in the interior of this shape there are wires connecting these terminals. This what he calls a wiring diagram.

You compose these wiring diagrams by pasting other wiring diagrams into each of the small circles.

The relationship with our Frobenius monoid diagrams is pretty simple: we draw our ‘wiring diagrams’ in a square, with the terminals on the left and terminals on the right. To get a Spivak-approved wiring diagram, glue the top and bottom edges of this square together, then flatten the cylinder you get down into an annulus, with the -side on the inside and -side on the outside. If you can imagine gluing opposite edges of the inside circle together to divide it into two small circles accordingly, and so on.

Relational algebras of type A

Algebras for wiring diagrams tell you what components you have available to wire together with your diagrams. An algebra for the operad of wiring diagrams is an operad homomorphism

What does this look like? Just like a functor for categories, it assigns to each natural number a set, and each wiring diagram a function.

In work related to decorated cospans (such as our paper on circuits or John and Jason’s work on signal flow diagrams), our semantics usually is constructed from a field of values—not a physicist’s ‘field’, bt an algebraist’s sort of ‘field’, where you can add, multiply, subtract and divide. For example, we like being able to assign a real number like a velocity, or potential, or current to a variable. This gives us vector spaces and a bunch of nice linear-algebraic structures.

Spivak works more generally: he’s interested in the structure when you just have a set of values. While this means we can’t do some of the nice things we could do with a field, it also means this framework can do things like talk about logic gates, where the variables are boolean ones, or number theoretic questions, where you’re interested in the natural numbers.

So to discuss semantics we pick a set of values, such as the real numbers or natural numbers or booleans or colors. We imagine then associating elements of this set to each wire in a wiring diagram. More technically, the algebra

then maps each finite set to the power set of the set of functions

On the morphisms (the wiring diagrams themselves), this functor behaves as follows. Note that a function () can be thought of as an ‘X-vector’ of ‘A-coordinates’. A wiring diagram is just a cospan

in so it can be thought of as some compares

followed by some copies

Thus, given a wiring diagram we can consider a partial function that maps an -vector to the -vector by doing these compares, and if it passes them does the copies and returns the resulting -vector, but if not returns ‘undefined’. We can then define a map which takes a set of -vectors to its image under this partial function.

This semantics is called the relational -algebra of type A. We can think of it as being like the ‘light operations’ fragment of the signal flow calculus. By ‘light operations’, we mean the operations of duplication and deletion, which form a cocommutative comonoid:

and their time-reversed versions, ‘coduplication’ and ‘codeletion’, which form a commutatative monoid:

These fit together to form a Frobenius monoid, meaning that these equations hold:

And it’s actually extra-special, meaning that these equations hold:

(If you don’t understand these hieroglyphics, please reread our post about categories in control theory, and ask some questions!)

Note that we can’t do the ‘dark operations’, because we only have a set of values, not a field, and the dark operations involve addition and zero!

Operads and the behavioral approach

In formulating Frobenius monoids this way, Spivak achieves something that we’ve been working hard to find ways to achieve: a separation of the behavioral structure from the interconnection structure.

What do I mean by this? In his ‘behavioral approach‘, Willems makes the point that for all their elaborate and elegant formulation, in the end physical laws just come down to dividing the set of what might a priori be possible (the ‘universum’) into the set of things that actually are possible (the ‘behavior’), and the set of things that aren’t). Here the universum is the set : a priori, on each of the wires in we might associate any value of For example, to the two wires at the ends of a resistor, we might a priori associate any pair of currents. But physical law, here Kirchhoff’s current law, says otherwise: the currents must be equal and opposite. So the ‘behavior’ is the subset of the universum

So you can say that to each object in the operad of wiring diagrams the relational algebra of type associates the set of possible behaviors—the universum is ( forms some sort of meta-universum, where you can discuss physical laws about physical laws, commonly called ‘principles’.)

The second key aspect of the behavioral approach is that the behaviors of larger systems can be constructed from the behaviors of its subsystems, if we understand the so-called ‘interconnection structure’ well enough. This is a key principle in engineering: we build big, complicated systems from a much smaller set of components, whether it be electronics from resistors and inductors, or mechanical devices from wheels and rods and ropes, or houses from Lego bricks. The various interconnection structures here are the wiring diagrams, and our relational algebras say they act by what Willems calls ‘variable sharing’.

This division between behavior and interconnection motivates the decorated cospan construction (where the decorations are the ‘components’, the cospans the ‘interconnection’) and also the multigraph categories discussed by Aleks Kissinger (where morphisms are the ‘components’, and the Frobenius monoid operations are the ‘interconnection’):

• Aleks Kissinger, Finite matrices are complete for (dagger-)multigraph categories.

So it’s good to have this additional way of thinking about things in our repertoire: operads describe ‘interconnection’, their algebras ‘behaviors’.

The separation Spivak achieves, however, seems to me to come at the cost of neat ways to talk about individual components, and perhaps this can be seen as the essential difference between the two approaches. By including our components as morphisms, we can talk more carefully about them and additional structure individual components have. On the other hand, by lumping all the components into the objects, Spivak can talk more carefully about how the interconnection structure acts on all behaviors at once.

Other operads of wiring diagrams

One advantage of the operad approach is that you can easily tweak your operad to talk about different sorts of network structure. Sometimes you can make similar adjustments with decorated cospans too, such as working over the category of typed finite sets, rather than just finite sets, to discuss networks in which wires have types, and only wires of the same types can be connected together. A physical example is a model of a hydroelectric power plant, where you don’t want to connect a water pipe with an electrical cable! This is also a common technique in computer science, where you don’t want to try to multiply two strings of text, or try to interpret a telephone number as a truth value.

But some modifications are harder to do with decorated cospans. In some other papers, Spivak employs a more restricted operad of wiring diagrams, in which joining wires and terminating wires is not allowed, among other things. He uses this to formalise graphical languages for certain types of discrete-time processes, open dynamical systems, including mode-dependent ones.

For more detail, read these:

• Brendan Fong, Decorated cospans.

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

Adjoint School 2024

Are you interested in applying category-theoretic methods to problems outside of pure mathematics? Apply to the Adjoint School!

Apply here. And do it soon.

• December 31, 2023. Application Due.

• February – May, 2024. Learning Seminar.

• June 10 – 14, 2024. In-person Research Week at the University of Oxford, UK.

Participants are divided into four-person project teams. Each project is guided by a mentor and a teaching assistant. The Adjoint School has two main components: an online learning seminar that meets regularly between February and June, and an in-person research week held in the summer adjacent to the Applied Category Theory Conference.

During the learning seminar you will read, discuss, and respond to papers chosen by the project mentors. Every other week a pair of participants will present a paper which will be followed by a group discussion. After the learning seminar each pair of participants will also write a blog post, based on the paper they presented, for The n-Category Café.

Projects and Mentors:

• Properties of Double Fibrations – Mentor: Dorette Pronk

• Application of Skew Monoidal Categories – Mentor: Niccolò Veltri

• Critical Pairs for String Diagram Rewriting – Mentor: Koko Muroya

• Modelling Uncertainty with Markov Categories – Mentor: Paolo Perrone

You can see more information about research projects at https://adjointschool.com/2024.html

Organizers:

• Ana Luiza da Conceição Tenorio
• Nathan Haydon
• Ari Rosenfield
• Elena Dimitriadis Bermejo

Lectures on Applied Category Theory

Want to learn applied category theory? You can now read my lectures here:

• Lectures on applied category theory

There are a lot of them, but each one is bite-sized and basically covers just one idea. They’re self-contained, but you can also read them along with Fong and Spivak’s free book to get two outlooks on the same material:

• Brendan Fong and David Spivak, Seven Sketches in Compositionality: An Invitation to Applied Category Theory.

Huge thanks go to Simon Burton for making my lectures into nice web pages! But they still need work. If you see problems, please let me know.

Here’s a problem: I need to include more of my ‘Puzzles’ in these lectures. None of the links to puzzles work. Students in the original course also wrote up answers to all of these puzzles, and to many of Fong and Spivak’s exercises. But it would take quite a bit of work to put all those into webpage form, so I can’t promise to do that. 😢

Here are the lectures:

Chapter 1: Ordered Sets

• Lecture 1 – Introduction

• Lecture 2 – What is Applied Category Theory?

• Lecture 3 – Preorders

• Lecture 4 – Galois Connections

• Lecture 5 – Galois Connections

• Lecture 6 – Computing Adjoints

• Lecture 7 – Logic

• Lecture 8 – The Logic of Subsets

• Lecture 9 – Adjoints and the Logic of Subsets

• Lecture 10 – The Logic of Partitions

• Lecture 11 – The Poset of Partitions

• Lecture 12 – Generative Effects

• Lecture 13 – Pulling Back Partitions

• Lecture 14 – Adjoints, Joins and Meets

• Lecture 15 – Preserving Joins and Meets

• Lecture 16 – The Adjoint Functor Theorem for Posets

• Lecture 17 – The Grand Synthesis

Chapter 2: Resource Theories

• Lecture 18 – Resource Theories

• Lecture 19 – Chemistry and Scheduling

• Lecture 20 – Manufacturing

• Lecture 21 – Monoidal Preorders

• Lecture 22 – Symmetric Monoidal Preorders

• Lecture 23 – Commutative Monoidal Posets

• Lecture 24 – Pricing Resources

• Lecture 25 – Reaction Networks

• Lecture 26 – Monoidal Monotones

• Lecture 27 – Adjoints of Monoidal Monotones

• Lecture 28 – Ignoring Externalities

• Lecture 29 – Enriched Categories

• Lecture 30 – Preorders as Enriched Categories

• Lecture 31 – Lawvere Metric Spaces

• Lecture 32 – Enriched Functors

• Lecture 33 – Tying Up Loose Ends

Chapter 3: Databases

• Lecture 34 – Categories

• Lecture 35 – Categories versus Preorders

• Lecture 36 – Categories from Graphs

• Lecture 37 – Presentations of Categories

• Lecture 38 – Functors

• Lecture 39 – Databases

• Lecture 40 – Relations

• Lecture 41 – Composing Functors

• Lecture 42 – Transforming Databases

• Lecture 43 – Natural Transformations

• Lecture 44 – Categories, Functors and Natural Transformations

• Lecture 45 – Composing Natural Transformations

• Lecture 46 – Isomorphisms

• Lecture 47 – Adjoint Functors

• Lecture 48 – Adjoint Functors

• Lecture 49 – Kan Extensions

• Lecture 50 – Left Kan Extensions

• Lecture 51 – Right Kan Extensions

• Lecture 52 – The Hom-Functor

• Lecture 53 – Free and Forgetful Functors

• Lecture 54 – Tying Up Loose Ends

Chapter 4: Collaborative Design

• Lecture 55 – Enriched Profunctors and Collaborative Design

• Lecture 56 – Feasibility Relations

• Lecture 57 – Feasibility Relations

• Lecture 58 – Composing Feasibility Relations

• Lecture 59 – Cost-Enriched Profunctors

• Lecture 60 – Closed Monoidal Preorders

• Lecture 61 – Closed Monoidal Preorders

• Lecture 62 – Enriched Profunctors

• Lecture 63 – Composing Enriched Profunctors

• Lecture 64 – The Category of Enriched Profunctors

• Lecture 65 – Collaborative Design

• Lecture 66 – Collaborative Design

• Lecture 67 – Feedback in Collaborative Design

• Lecture 68 – Feedback in Collaborative Design

• Lecture 69 – Feedback in Collaborative Design

• Lecture 70 – Tensoring Enriched Profunctors

• Lecture 71 – Caps and Cups for Enriched Profunctors

• Lecture 72 – Monoidal Categories

• Lecture 73 – String Diagrams and Strictification

• Lecture 74 – Compact Closed Categories

• Lecture 75 – The Grand Synthesis

• Lecture 76 – The Grand Synthesis

• Lecture 77 – The End? No, the Beginning!

Chemistry and Invariant Theory

In an alternative history of the world, perhaps quantum mechanics could have been discovered by chemists following up on the theories of two mathematicians from the late 1800s: Sylvester, and Gordan.

Both are famous for their work on invariant theory, which we would now call part of group representation theory. For example, we now use the Clebsch–Gordan coefficients to understand the funny way angular momentum ‘adds’ when we combine two quantum systems. This plays a significant role in physical chemistry, though Gordan never lived to see that.

But Sylvester already wanted to connect chemistry to invariant theory back in 1878! He published a paper on it, in the first issue of a journal he himself founded:

• James Joseph Sylvester, On an application of the new atomic theory to the graphical representation of the invariants and covariants of binary quantics, with three appendices, American Journal of Mathematics 1 (1878), 64–104. (Available on JSTOR.)

The title suggests he is applying ideas from chemistry to invariant theory, rather than the other way around! I haven’t absorbed the paper, but this impression is somewhat confirmed by these passages:

To those unacquainted with the laws of atomicity I recommend Dr. Frankland’s Lecture Notes for Chemical Students, vols. 1 and 2, London (Van Voorst), a perfect storehouse of information on the subject arranged in the most handy order and put together and explained with true scientific accuracy and precision.

and then:

The more I study Dr. Frankland’s wonderfully beautiful little treatise the more deeply I become impressed with the harmony or homology (I might call it, rather than analogy) which exists between the chemical and algebraical theories. In travelling my eye up and down the illustrated pages of “the Notes,” I feel as Aladdin might have done in walking in the garden where every tree was laden with precious stones, or as Caspar Hauser when first brought out of his dark cellar to contemplate the glittering heavens on a starry night. There is an untold treasure of hoarded algebraical wealth potentially contained in the results achieved by the patient and long continued labor of our unconscious and unsuspected chemical fellow-workers.

So, he thinks the chemists may have found an ‘untold treasure of algebraical wealth’. What is this?

First he notes that you can use graphs to describe molecules: vertices represent atoms, and edges represent bonds.

This idea, utterly commonplace now, may have been only four years old when Sylvester published his work, since Wikipedia credits the use of graphs for describing molecules to this paper:

• Arthur Cayley, On the mathematical theory of isomers, Philosophical Magazine 47 (1874), 444–446.

Surely it’s not a complete coincidence that Sylvester was friends with Cayley, and that Sylvester was the first to use the term ‘graph’ to mean a bunch of vertices connected by edges!

But Sylvester noticed you can also use graphs to describe ways of building scalars from tensors: a vertex with n edges coming out is a tensor with n indices, and an edge between vertices means you sum over a repeated index, as in the ‘Einstein summation convention’. This idea is often attributed to Penrose, who explained it more clearly much later:

• Penrose on spin networks.

Still later, Penrose’s spin networks and the theory of Feynman diagrams were unified via ‘string diagrams’ in category theory. I explain the story and the math here:

• John Baez and Aaron D. Lauda, A prehistory of n-categorical physics, in Deep Beauty: Mathematical Innovation and the Search for an Underlying Intelligibility of the Quantum World, ed. Hans Halvorson, Cambridge U. Press, Cambridge, 2011, pp. 13–128.

So, we can think of Sylvester’s chemistry-inspired work as another obscure chapter in the prehistory of n-categorical physics!

To be precise, in Sylvester’s setup a vertex with n edges out represents an atom with n bonds coming out, but also a binary quantic, meaning an element of where is a 2-dimensional vector space with an inner product on it. He notes that hydrogen, chlorine, bromine, and potassium have n = 1, oxygen, zinc, and magnesium have n = 2, and so on.

The inner product on lets us raise or lower indices in tensors, so we don’t have to worry about which indices are superscripts and which are subscripts, which is usually a major aspect of the Einstein summation convention. In other words, it lets us identify with its dual , so we don’t have to worry about the difference between covariant and contravariant tensors.

It seems that by this method, Sylvester was able to see diagrams of molecules as recipes for building scalars from tensors! Here’s a nice page containing 45 separate figures explained in his paper:

But it wasn’t just Sylvester. Clifford, famous for inventing Clifford algebras, also thought about chemistry and invariant theory. In fact he wrote a letter about it to Sylvester! Sylvester published part of this along with his own work in the first issue of his journal:

• William Kingdon Clifford, Extract of a letter to Mr. Sylvester from Prof. Clifford of University College, London, American Journal of Mathematics 1 (1878), 126–128. (Available on JSTOR.)

Sylvester was so excited that he published this without Clifford’s permission, writing:

The subjoined matter is so exceedingly interesting and throws such a flood of light on the chemico-algebraical theory, that I have been unable to resist the temptation to insert it in the Journal, without waiting to obtain the writer’s permission to do so, for which there is not time available between the date of its receipt and my proximate departure for Europe. It is written from Gibraltar, whither Professor Clifford has been ordered to recruit his health, a treasure which he ought to feel bound to guard as a sacred trust for the benefit of the whole mathematical world.

I have not managed to understand Clifford’s ideas yet, but they may have been better than Sylvester’s—though unfortunately not developed, due to Clifford’s untimely death one year later in 1879. Olver and Shakiban write:

Although Sylvester envisioned his theory as the future of chemistry, it is Clifford’s graph theory that, with one slight but important modification, could have become a useful tool in computational invariant theory. The algebro-chemical theory reduces computations of invariants to methods of graph theory. Our thesis is that the correct framework for the subject is to use digraphs or “directed molecules” as the fundamental objects. One can ascribe both a graph theoretical as well as a chemical interpretation.

This is from here:

• Peter J. Olver and Cherzhad Shakiban, Graph theory and classical invariant theory, Advances in Mathematics 75 (1989), 212–245.

It sounds like what Clifford realized is that by using a directed graph we get a better theory that lets us drop the inner product on Having graphs with directed edges lets the graphical notation distinguish between covariant and contravariant tensors.

Now let’s jump forward a decade or two! At some point Paul Gordan read the work of Clifford and Sylvester and concluded that invariant theory could contribute to the understanding of chemical valence. But his own ideas were somewhat different. In 1900 he and his student W. Alexejeff wrote an article about this:

• Paul Gordan and W. Alexejeff, Übereinstimmung der Formeln der Chemie und der Invariantentheorie, Zeitschrift für Physikalische Chemie, 35 (1900), 610–633.

In 2006, Wormer and Paldus wrote:

The origins of the coupling problem for angular momenta can be traced back to the early—purely mathematical—work on invariant theory by (Rudolf Friedrich) Alfred Clebsch (1833–1872) and Paul (Albert) Gordan (1837–1912), see Section 2.5. Even before the birth of quantum mechanics the formal analogy between chemical valence theory and binary invariant theory was recognized by eminent mathematicians as Sylvester, Clifford, and Gordan and Alexejeff. The analogy, lacking a physical basis at the time, was criticised heavily by the mathematician E. Study and ignored completely by the chemistry community of the 1890s. After the advent of quantum mechanics it became clear, however, that chemical valences arise from electron–spin couplings … and that electron spin functions are, in fact, binary forms of the type studied by Gordan and Clebsch.

I learned of this quote from James Dolan, who happened to be studying the work of Eduard Study, who is mostly famous for his work on the so-called dual numbers, the free algebra on one generator that squares to zero. The paper by Wormer and Paldus is here:

• Paul E. S. Wormer and Josef Paldus, Angular momentum diagrams, Advances in Quantum Chemistry 51 (2006), 51–124.

Here’s another paper I should read:

• Karen Hunger Parshall, Chemistry through invariant theory? James Joseph Sylvester’s mathematization of the atomic theory, in Experiencing Nature: Proceedings of a Conference in Honor of Allen G. Debus, Springer, Berlin, 1997.

Sylvester was a colorful and fascinating character. For example, he entered University College London at the age of 14. But after just five months, he was accused of threatening a fellow student with a knife in the dining hall! His parents took him out of college and waited for him to grow up a bit more.

He began studies in Cambridge at 17. Despite being ill for 2 years, he came in second in the big math exam called the tripos. But he couldn’t get a degree… because he was Jewish.

In 1841, he was awarded a BA and an MA by Trinity College Dublin. In the same year he moved to the United States to become a professor of mathematics at the University of Virginia.

After just a few months, a student reading a newspaper in one of Sylvester’s lectures insulted him. Sylvester struck him with a sword stick. The student collapsed in shock. Sylvester thought he’d killed the guy! He fled to New York where one of his brothers was living.

Later he came back to Virginia. But according an online biography, “the abuse suffered by Sylvester from this student got worse after this”. Soon he quit his job.

He returned to England and took up a job at a life insurance company. He needed a law degree for this job, and in his studies he met another mathematician, five years younger, studying law: Cayley! They worked together on matrices and invariant theory.

Sylvester only got another math job in 1855, at the Royal Military Academy of Woolwich. He was 41. At age 55 they made him retire—that was the rule—but for some reason the school refused to pay his pension!

The Royal Military Academy only relented and paid Sylvester his pension after a prolonged public controversy, during which he took his case to the letters page of The Times.

When he was 58, Cambridge University finally gave him his BA and MA.

At age 62, Sylvester went back to the United States to become the first professor of mathematics at the newly founded Johns Hopkins University in Baltimore, Maryland. His salary was $5,000—quite generous for the time.

He demanded to be paid in gold.

They wouldn’t pay him in gold, but he took the job anyway. At age 64, he founded the American Journal of Mathematics. At 69, he was invited back to England to become a professor at Oxford. He worked there until his death at age 83.

One thing I’ve always liked about Sylvester is that he invented lots of terms for mathematical concepts. Some of them have caught on: matrix, discriminant, invariant, totient, and Jacobian! Others have not: cyclotheme, meicatecticizant, tamisage and dozens more.

But only now am I realizing how Sylvester’s fertile imagination, inspired by chemistry, connected graph theory and invariant theory in ways that would later become crucial for physics.

Symposium on Compositional Structures 9

The Symposium on Compositional Structures is a nice informal conference series that happens more than once a year. You can now submit talks for this one.

• Ninth Symposium on Compositional Structures (SYCO 9), Como, Italy, 8-9 September 2022. Deadline to submit a talk: Monday 1 August 2022.

Apparently you can attend online but to give a talk you have to go there. Here are some details:

The Symposium on Compositional Structures (SYCO) is an interdisciplinary series of 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. Previous SYCO events have been held in Birmingham, Strathclyde, Oxford, Chapman, Leicester and Tallinn.

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. Submissions is easy, with no formatting 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:

• logical methods in computer science, including classical and quantum programming, type theory, concurrency, natural language processing and machine learning;
• graphical calculi, including string diagrams, Petri nets and reaction networks;
• languages and frameworks, including process algebras, proof nets, type theory and game semantics;
• abstract algebra and pure category theory, including monoidal category theory, higher category theory, operads, polygraphs, and relationships to homotopy theory;
• quantum algebra, including quantum computation and representation theory;
• tools and techniques, including rewriting, formal proofs and proof assistants, and game theory;
• industrial applications, including case studies and real-world problem descriptions.

Important dates

All deadlines are 23:59 Anywhere on Earth.

Submission deadline: Monday 1 August
Author notification: Monday 8 August 2022
Symposium dates: Thursday 8 and Friday 9 September 2022

Submission instructions

Submissions are by EasyChair, via the SYCO 9 submission page:

• https://easychair.org/my/conference?conf=syco9

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. Think creatively: you could submit a recent paper, or notes on work in progress, or even a recent Masters or PhD thesis.

In the event that more good-quality submissions are received than can be accommodated in the timetable, the programme committee may choose to defer some submissions to a future meeting, rather than reject them. Deferred submissions can be re-submitted to any future SYCO meeting, where they will not need peer review, and where they will be prioritised for inclusion in the programme. Meetings will be held sufficiently frequently to avoid a backlog of deferred papers.

If you have a submission which was deferred from a previous SYCO meeting, it will not automatically be considered for SYCO 9; you still need to submit it again through EasyChair. When submitting, append the words “DEFERRED FROM SYCO X” to the title of your paper, replacing “X” with the appropriate meeting number. There is no need to attach any documents.

Programme committee

The PC chair is John van de Wetering, Radboud University. The Programme Committee will be announced soon.

Steering committee

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

Adjoint School 2022

Every year since 2018 we’ve been having annual courses on applied category theory where you can do research with experts. It’s called the Adjoint School.

You can apply to be a student at the 2022 Adjoint School now, and applications are due February 4th! Go here:

• 2022 Adjoint School: application.

The school will be run online from February to June, 2022, and then—coronavirus permitting—there will be in-person research at the University of Strathclyde in Glasgow, Scotland the week of July 11 – 15, 2022. This is also the location of the applied category theory conference ACT2022.

The 2022 Adjoint School is organized by Angeline Aguinaldo, Elena Di Lavore, Sophie Libkind, and David Jaz Myers. You can read more about how it works here:

• About the Adjoint School.

There are four topics to work on, and you can see descriptions of them below.

Who should apply?

Anyone, from anywhere in the world, who is interested in applying category-theoretic methods to problems outside of pure mathematics. This is emphatically not restricted to math students, but one should be comfortable working with mathematics. Knowledge of basic category-theoretic language—the definition of monoidal category for example—is encouraged.

We will consider advanced undergraduates, PhD students, post-docs, as well as people working outside of academia. Members of groups which are underrepresented in the mathematics and computer science communities are especially encouraged to apply.

Also check out our inclusivity statement.

Topic 1: Compositional Thermodynamics

Mentors: Spencer Breiner and Joe Moeller

TA: Owen Lynch

Description: Thermodynamics is the study of the relationships between heat, energy, work, and matter. In category theory, we model flows in physical systems using string diagrams, allowing us to formalize physical axioms as diagrammatic equations. The goal of this project is to establish such a compositional framework for thermodynamical networks. A first goal will be to formalize the laws of thermodynamics in categorical terms. Depending on the background and interest of the participants, further topics may include the Carnot and Otto engines, more realistic modeling for real-world systems, and software implementation within the AlgebraicJulia library.

Readings:

• John C. Baez, Owen Lynch, and Joe Moeller, Compositional thermostatics.

• F. William Lawvere, State categories, closed categories and the existence of semi-continuous entropy functions.

Topic 2: Fuzzy Type Theory for Opinion Dynamics

Mentor: Paige North

TA: Hans Reiss

Description: When working in type theory (or most logics), one is interested in proving propositions by constructing witnesses to their incontrovertible truth. In the real world, however, we can often only hope to understand how likely something is to be true, and we look for evidence that something is true. For example, when a doctor is trying to determine if a patient has a certain condition, they might ask certain questions and perform certain tests, each of which constitutes a piece of evidence that the patient does or does not have that condition. This suggests that a fuzzy version of type theory might be appropriate for capturing and analyzing real-world situations. In this project, we will explore the space of fuzzy type theories which can be used to reason about the fuzzy propositions of disease and similar dynamics.

Readings:

• Daniel R. Grayson, An introduction to univalent foundations for mathematicians.

• Jakob Hansen and Robert Ghrist, Opinion dynamics on discourse sheaves.

Topic 3: A Compositional Theory of Timed and Probabilistic Processes: CospanSpan(Graph)

Mentor: Nicoletta Sabadini

TA: Mario Román

Description: Span(Graph), introduced by Katis, Sabadini and Walters as a categorical algebra for automata with interfaces, provides, in a very intuitive way, a compositional description of hierarchical networks of interacting components with fixed topology. The algebra also provides a calculus of connectors, with an elegant description of signal broadcasting. In particular, the operations of “parallel with communication” (that allows components to evolve simultaneously, like connected gears), and “non-sequential feedback” (not considered in Kleene’s algebra for classical automata) are fundamental in modelling complex distributed systems such as biological systems. Similarly, the dual algebra Cospan(Graph) allows us to compose systems sequentially. Hence, the combined algebra CospanSpan(Graph), which extends Kleene’s algebra for classical automata, is a general algebra for reconfigurable networks of interacting components. Still, some very interesting aspects and possible applications of this model deserve a better understanding:

• How can timed actions and probability be combined in CospanSpan(Graph)?

• If not, can we describe time-varying probability in a compositional setting?

• Which is the possible role of “parallel with communication” in understanding causality?

Readings:

• L. de Francesco Albasini, N. Sabadini, and R.F.C. Walters, The compositional construction of Markov processes II.

• A. Cherubini, N. Sabadini, and R.F.C. Walters, Timing in the Cospan-Span model.

Topic 4: Algebraic Structures in Logic and Relations

Mentor: Filippo Bonchi

Description: Fox’s theorem provides a bridge between structures defined by universal properties (products in a category) and structures specified by algebraic means (comonoids in a symmetric monoidal category). Such a theorem has recently received a renewed interest as the algebraic structures allows for reasoning in terms of string diagrams. While the universal properties underlying logical theories have been extensively studied in categorical logic, their algebraic counterparts have been the objects of fewer investigations. This raises a natural question: can we capture the universal content of logical theories algebraically? In other words, what are the ‘Fox theorems’ for logic? In this project, we attempt to answer to this question by taking as starting point Cartesian bicategories which serves as algebraic setting for regular logic.

Readings:

• Aurelio Carboni and R. F. C. Walters, Cartesian bicategories I.

• Filippo Bonchi, Jens Seeber and Pawel Sobocinski, Graphical conjunctive queries.

• Filippo Bonchi, Dusko Pavlovic and Pawel Sobocinski, Functorial semantics for relational theories.

ACT2020 Tutorial Day

If you’re wanting to learn some applied category theory, register for the tutorials that are taking place on July 5, 2020 as part of ACT2020!

Applied category theory offers a rigorous mathematical language and toolset for relating different concepts from across math, science, and technology. For example, category theory finds common patterns between geometry (shapes), algebra (equations), numbers, logic, probability, etc. Applied category theory (ACT) looks for how those very same patterns extend outward to data, programs, processes, physics, linguistics, and so on—things we see in the real world. The field is currently growing, as new applications and common patterns are being found all the time. When you understand these ideas, more of your intuitions about the world can be made rigorous and thus be communicated at a larger scale. This in turn gives our community a chance to solve larger and more complex scientific, technological, and maybe even societal problems.

This year’s international applied category theory conference ACT2020 is having a tutorial day, meant to introduce newcomers to applied category theory. Tutorial day will take place on July 5 and will include a few main topics that will be taught semi-traditionally (via presentation, exercises, and discussion) over Zoom, as well as mentors who will be available throughout the day to work with smaller groups and/or individuals. We invite you to sign up here if you’re interested, so we can keep you posted. Hope to see you there!

The four courses will be roughly as follows:

• David Spivak: categorical databases for introducing sets, functions, categories, and functors.

• Fabrizio Genovese: string diagrams as a graphical language for category theory.

• Emily Riehl: the Yoneda lemma in the context of matrices.

• Paolo Perrone: monads and comonads.

Star-Autonomous Envelopes

In the fourth talk of the ACT@UCR seminar, Michael Shulman told us how to create nice string diagams for any closed symmetric monoidal category.

Mike had to teach right after his talk, but he rejoined us for discussions later at the Category Theory Community Server, here:

https://categorytheory.zulipchat.com/#narrow/stream/229966-ACT.40UCR-seminar/topic/April.2022nd.3A.20Michael.20Shulman

You can view or join the conversation there if you sign in.

You can see his slides here, or download a video of his talk here, or watch the video here:

• April 22, Michael Shulman, Star-autonomous envelopes.

Abstract. Symmetric monoidal categories with duals, a.k.a. compact monoidal categories, have a pleasing string diagram calculus. In particular, any compact monoidal category is closed with [A,B] = (A* ⊗ B), and the transpose of A ⊗ B → C to A → [B,C] is represented by simply bending a string. Unfortunately, a closed symmetric monoidal category cannot even be embedded fully-faithfully into a compact one unless it is traced; and while string diagram calculi for closed monoidal categories have been proposed, they are more complicated, e.g. with “clasps” and “bubbles”. In this talk we obtain a string diagram calculus for closed symmetric monoidal categories that looks almost like the compact case, by fully embedding any such category in a star-autonomous one (via a functor that preserves the closed structure) and using the known string diagram calculus for star-autonomous categories. No knowledge of star-autonomous categories will be assumed.

His talk is based on this paper:

• Michael Shulman, Star-autonomous envelopes.

This subject is especially interesting to me since Mike Stay and I introduced string diagrams for closed monoidal categories in a somewhat ad hoc way in our Rosetta Stone paper—but the resulting diagrams required clasps and bubbles:

This is the string diagram for beta reduction in the cartesian closed category coming from the lambda calculus.

ACT@UCR Seminar

We’re having a seminar on applied category theory at U. C. Riverside, organized by Joe Moeller and Christian Williams.

It will take place on Wednesdays at 5 pm UTC, which is 10 am in California or 1 pm on the east coast of the United States, or 6 pm in England. It will be held online via Zoom, here:

https://ucr.zoom.us/j/607160601

We’ll have discussions on the Category Theory Community Server.

All talks will be recorded and put on YouTube here:

https://www.youtube.com/channel/UCUQlS-R4O094jP0sGHDnrjA

Here are the talks:

• April 1st, John Baez: Structured cospans and double categories.

Abstract. One goal of applied category theory is to better understand networks appearing throughout science and engineering. Here we introduce “structured cospans” as a way to study networks with inputs and outputs. Given a functor L: A → X, a structured cospan is a diagram in X of the form

L(a) → x ← L(b).

If A and X have finite colimits and L is a left adjoint, we obtain a symmetric monoidal category whose objects are those of A and whose morphisms are certain equivalence classes of structured cospans. However, this arises from a more fundamental structure: a symmetric monoidal double category where the horizontal 1-cells are structured cospans, not equivalence classes thereof. We explain the mathematics and illustrate it with an example from epidemiology.

You can see the slides here, or download a video here, or watch the video here:

The talk was based on these papers:

• John Baez and Kenny Courser, Structured cospans.
• Kenny Courser, Open Systems: a Double Categorical
Perspective.

• April 8th, Prakash Panangaden: A categorical view of conditional expectation.

Abstract. This talk is a fragment from a larger work on approximating Markov processes. I will focus on a functorial definition of conditional expectation without talking about how it was used. We define categories of cones—which are abstract versions of the familiar cones in vector spaces—of measures and related categories cones of L_p functions. We will state a number of dualities and isomorphisms between these categories. Then we will define conditional expectation by exploiting these dualities: it will turn out that we can define conditional expectation with respect to certain morphisms. These generalize the standard notion of conditioning with respect to a sub-sigma algebra. Why did I use the plural? Because it turns out that there are two kinds of conditional expectation, one of which looks like a left adjoint (in the matrix sense not the categorical sense) and the other looks like a right adjoint. I will review concepts like image measure, Radon-Nikodym derivatives and the traditional definition of conditional expectation. This is joint work with Philippe Chaput, Vincent Danos and Gordon Plotkin.

You can see the slides here, or download a video of the talk here, or watch the video here:

His talk was based on this paper:

• Philippe Chaput, Vincent Danos, Prakash Panangaden and Gordon Plotkin, Approximating Markov processes by averaging, in International Colloquium on Automata, Languages, and Programming, Springer, Berlin, 2009.

• April 15, Jules Hedges: Open games: the long road to practical applications.

Abstract. I will talk about open games, and the closely related concepts of lenses/optics and open learners. My goal is to report on the successes and failures of an ongoing effort to try to realise the often-claimed benefits of categories and compositionality in actual practice. I will introduce what little theory is needed along the way. Here are some things I plan to talk about:

— Lenses as an abstraction of the chain rule

— Comb diagrams

— Surprising applications of open games: Bayesian inference, value function iteration

— The state of tool support

— Open games in their natural habitat: microeconomics

— Sociological aspects of working with economics

You can see the slides here, or download a video of the talk here, or watch the video here:

• April 22, Michael Shulman, Star-autonomous envelopes.

Abstract. Symmetric monoidal categories with duals, a.k.a. compact monoidal categories, have a pleasing string diagram calculus. In particular, any compact monoidal category is closed with [A,B] = (A* ⊗ B), and the transpose of A ⊗ B → C to A → [B,C] is represented by simply bending a string. Unfortunately, a closed symmetric monoidal category cannot even be embedded fully-faithfully into a compact one unless it is traced; and while string diagram calculi for closed monoidal categories have been proposed, they are more complicated, e.g. with “clasps” and “bubbles”. In this talk we obtain a string diagram calculus for closed symmetric monoidal categories that looks almost like the compact case, by fully embedding any such category in a star-autonomous one (via a functor that preserves the closed structure) and using the known string diagram calculus for star-autonomous categories. No knowledge of star-autonomous categories will be assumed.

You can see the slides here, or download a video of the talk here, or watch the video here:

His talk is based on this paper:

• Michael Shulman, Star-autonomous envelopes.

• April 29, Gershom Bazerman, A localic approach to the semantics of dependency, conflict, and concurrency.

Abstract. Petri nets have been of interest to applied category theory for some time. Back in the 1980s, one approach to their semantics was given by algebraic gadgets called “event structures.” We use classical techniques from order theory to study event structures without conflict restrictions (which we term “dependency structures with choice”) by their associated “traces”, which let us establish a one-to-one correspondence between DSCs and a certain class of locales. These locales have an internal logic of reachability, which can be equipped with “versioning” modalities that let us abstract away certain unnecessary detail from an underlying DSC. With this in hand we can give a general notion of what it means to “solve a dependency problem” and combinatorial results bounding the complexity of this. Time permitting, I will sketch work-in-progress which hopes to equip these locales with a notion of conflict, letting us capture the full semantics of general event structures in the form of homological data, thus providing one avenue to the topological semantics of concurrent systems. This is joint work with Raymond Puzio.

You can see the slides here, or download a video of the talk here, or watch the video here:

• May 6, Sarah Rovner-Frydman: Separation logic through a new lens.

Abstract. Separation logic aims to reason compositionally about the behavior of programs that manipulate shared resources. When working with separation logic, it is often necessary to manipulate information about program state in patterns of deconstruction and reconstruction. This achieves a kind of “focusing” effect which is somewhat reminiscent of using optics in a functional programming language. We make this analogy precise by showing that several interrelated techniques in the literature for managing these patterns of manipulation can be derived as instances of the general definition of profunctor optics. In doing so, we specialize the machinery of profunctor optics from categories to posets and to sets. This simplification makes most of this machinery look more familiar, and it reveals that much of it was already hiding in separation logic in plain sight.

You can see the slides here, or download a video of the talk here, or watch the video here:

• May 13, Tai-Danae Bradley: Formal concepts vs. eigenvectors of density operators.

Abstract. In this talk, I’ll show how any probability distribution on a product of finite sets gives rise to a pair of linear maps called density operators, whose eigenvectors capture “concepts” inherent in the original probability distribution. In some cases, the eigenvectors coincide with a simple construction from lattice theory known as a formal concept. In general, the operators recover marginal probabilities on their diagonals, and the information stored in their eigenvectors is akin to conditional probability. This is useful in an applied setting, where the eigenvectors and eigenvalues can be glued together to reconstruct joint probabilities. This naturally leads to a tensor network model of the original distribution. I’ll explain these ideas from the ground up, starting with an introduction to formal concepts. Time permitting, I’ll also share how the same ideas lead to a simple framework for modeling hierarchy in natural language. As an aside, it’s known that formal concepts arise as an enriched version of a generalization of the Isbell completion of a category. Oftentimes, the construction is motivated by drawing an analogy with elementary linear algebra. I like to think of this talk as an application of the linear algebraic side of that analogy.

You can see the slides here, or download a video of the talk here, or watch the video here:

Her talk is based on her thesis:

• Tai-Danae Bradley, At the Interface of Algebra and Statistics.

• May 20, Gordon Plotkin: A complete axiomatisation of partial differentiation

Abstract. We formalise the well-known rules of partial differentiation in a version of equational logic with function variables and binding constructs. We prove the resulting theory is complete with respect to polynomial interpretations. The proof makes use of Severi’s theorem that all multivariate Hermite problems are solvable. We also hope to present a number of related results, such as decidability and Hilbert-Post completeness.

You can see the slides here, or download a video of the talk here, or watch the video here:

• May 27, Simon Willerton: The Legendre–Fenchel transform from a category theoretic perspective.

Abstract. The Legendre-Fenchel transform is a classical piece of mathematics with many applications. In this talk I’ll show how it arises in the context of category theory using categories enriched over the extended real numbers . It turns out that it arises out of nothing more than the pairing between a vector space and its dual in the same way that the many classical dualities (e.g. in Galois theory or algebraic geometry) arise from a relation between sets.

I won’t assume knowledge of the Legendre-Fenchel transform.

You can see his slides here, or download a video of the talk here, or watch the video here:

• June 3, Nina Otter: Values and inclusivity in the applied category theory community.

Abstract. Saddened by the current events, we are taking this opportunity to pause and reflect on what we can do to change the status quo and try to bring about real and long-lasting change. Thus, we are holding a discussion aimed at finding concrete solutions to make the Applied Category Theory community more inclusive, and also to reflect about the values that our community would like to stand for and endorse, in particular, in terms of which sources of funding go against our values. While this discussion is specific to the applied category theory community, we believe that many of the topics will be of interest also to people in other fields, and thus we welcome anybody with an interest to attend. The discussion will consist of two parts: we will have first several people give short talks to discuss common issues that we need to address, as well as present specific plans for initiatives that we could take. We believe that the current pandemic, and the fact that all activities are now taking place remotely, gives us the opportunity to involve people who would otherwise find it difficult to travel, because of disabilities, financial reasons or care-taking responsibilities. Thus, now we have the opportunity to come up with new types of mentoring, collaborations, and many other initiatives that might have been difficult to envision until just a couple of months ago. The second part of the discussion will take place on the category theory community server, and its purpose is to allow for a broader participation in the discussion, and ideally during this part we will be able to flesh out in detail the specific initiatives that have been proposed in the talks.

You can see the slides here, or download a video of the discussion here, or watch the video here: