Complex Adaptive System Design (Part 10)

guest post by John Foley

Though the Complex Adaptive System Composition and Design Environment (CASCADE) program concluded in Fall 2020, just this week two new articles came out reviewing the work and future research directions:

• John Baez and John Foley, Operads for designing systems of systems, Notices of the American Mathematical Society 68 (2021), 1005–1007.

• John Foley, Spencer Breiner, Eswaran Subrahmanian and John Dusel, Operads for complex system design specification, analysis and synthesis, Proceedings of the Royal Society A 477 (2021), 20210099.

Operads for Designing Systems of Systems

The first is short and sweet (~2 pages!), aimed at a general mathematical audience. It describes the motivation for CASCADE and how basic modeling issues for point-to-point communications led to the development network operads:

This figure depicts the prototypical example of this style of operad, the ‘simple network operad’, acting on an algebra of graphs whose nodes are endowed with locations and edges can be no longer than a fixed range limit. For more information, check out the article or Part 4 of this series.

For a quick, retrospective overview of CASCADE, this note is hard to beat, so I won’t repeat more here.

Operads for complex system design specification, analysis and synthesis

The second article is a full length review, aimed at a general applied science audience:

We introduce operads for design to a general scientific audience by explaining what the operads do relative to broadly applied techniques and how specific domain problems are modelled. Research directions are presented with an eye towards opening up interdisciplinary partnerships and continuing application-driven investigations to build on recent insights.

The review describes how operads apply to system design problems through three examples:

and concludes with a discussion of future research directions. The specification and synthesis examples come from applications of network operads in CASCADE, but the analysis example was contributed by collaborators Spencer Breiner and Eswaran Subrahmanian at the National Institute of Standards and Technology (NIST), who analyzed the Length Scale Interferometer (LSI) at NIST headquarters. Readers interested in a quick introduction to these examples should head directly to Section 3 of the review.

As we describe:

The present article captures an intermediate stage of technical maturity: operad-based design has shown its practicality by lowering barriers of entry for applied practitioners and demonstrating applied examples across many domains. However, it has not realized its full potential as an applied meta-language. Much of this recent progress is not focused solely on the analytic power of operads to separate concerns. Significant progress on explicit specification of domain models and techniques to automatically synthesize designs from basic building blocks has been made.

With this context, CASCADE’s contribution was prototyping general-purpose methods to specify basic building blocks and synthesize composite systems from atoms. By testing these methods against specific domain problems, we learned that domain-specific information should be exploited but systematically fitting together general-purpose and computationally efficient methods is challenging. Moreover, no reconciliation between the analytic point-of-view on operads for system design and the `generative’ perspective of network operads, which facilitate specification and synthesis, has been established. The review does not address how these threads might fit together precisely, but perhaps the answer looks something like this:

For more discussion of future research directions, please see Section 7 of the review, especially the open problems listed in 7f.

For readers that make it through the examples in Sections 4, 5 and 6 of the review but still want more, the following references provide additional details:

• John Baez, John Foley, Joe Moeller and Blake Pollard, Network models, Theory and Applications of Categories 35 (2020), 700–744.

• Spencer Breiner, Olivier Marie-Rose, Blake Pollard and Eswaran Subrahmanian, Modeling hierarchical system with operads, Electron. Proc. Theor. Comput. Sci. 323 (2020) 72–83.

• John Baez, John Foley and Joe Moeller, Network models from Petri nets with catalysts, Compositionality 1 (4) (2017).

---

Here’s the whole series of posts:

• Part 1. CASCADE: the Complex Adaptive System Composition and Design Environment.

• Part 2. Metron’s software for system design.

• Part 3. Operads: the basic idea.

• Part 4. Network operads: an easy example.

• Part 5. Algebras of network operads: some easy examples.

• Part 6. Network models.

• Part 7. Step-by-step compositional design and tasking using commitment networks.

• Part 8. Compositional tasking using category-valued network models.

• Part 9 – Network models from Petri nets with catalysts.

• Part 10 – Two papers reviewing the whole project.

Compositional Robotics (Part 2)

Very soon we’re having a workshop on applications of category theory to robotics:

• 2021 Workshop on Compositional Robotics: Mathematics and Tools, online, Monday 31 May 2021.

You’re invited! As of today it’s not too late to register and watch the talks online, and registration is free. Go here to register:

https://forms.gle/9v52EXgDFFGu3h9Q6

Here’s the schedule. All times are in UTC, so the show starts at 9:15 am Pacific Time:

Time (UTC)	Speaker	Title
16:15-16:30		Intro and plan of the workshop
16:30-17:10	Jonathan Lorand	Category Theory Basics
17:20-18:00	John Baez	Category Theory and Systems
	Breakout rooms
18:30-19:10	Andrea Censi & Gioele Zardini	Categories for Co-Design
19:20-20:00	David Spivak	Dynamic Interaction Patterns
	Breakout rooms
20:30-21:15	Aaron Ames	A Categorical Perspective on Robotics
21:30-22:15	Daniel Koditschek	Toward a Grounded Type Theory for Robot Task Composition
22:30-00:30	Selected speakers	Talks from open submissions

For more information go to the workshop website or my previous blog post on this workshop:

• Compositional robotics (part 1).

Category Theory and Systems

I’m giving a talk on Monday the 31st of May, 2021 at 17:20 UTC, which happens to be 10:20 am Pacific Time for me. You can see my slides here:

• Category theory and systems.

I’ll talk about how to describe open systems as morphisms in symmetric monoidal categories, and how to use ‘functorial semantics’ to describe the behavior of open systems.

It’s part of the 2021 Workshop on Compositional Robotics: Mathematics and Tools, and if you click the link you can see how to attend!  If you stick around for the rest of the workshop you’ll hear more concrete talks from people who really work on robotics. 

Geoengineering – The Tipping Point

Back in 2013 I wrote about how we are approaching a tipping point, where public opinion on geoengineering suddenly starts to shift:

Many express the fear that merely researching geoengineering schemes will automatically legitimate them, however hare-brained they are. There’s some merit to that fear. But I suspect that public opinion on geoengineering will suddenly tip from “unthinkable!” to “let’s do it now!” as soon as global warming becomes perceived as a real and present threat. This is especially true because oil, coal and gas companies have a big interest in finding solutions to global warming that don’t make them stop digging.

I argued that because of this, we need to start thinking hard about the issues now.

I think we should start serious research on geoengineering schemes, including actual experiments, not just calculations and simulations. I think we should do this with an open mind about whether we’ll decide that these schemes are good ideas or bad. Either way, we need to learn more about them. Simultaneously, we need an intelligent, well-informed debate about the many ethical, legal and political aspects.

I think this tipping point is getting very close now: close enough to be discussed in popular media. Like this:

• Ezra Klein, Should we dim the Sun? Will we even have a choice?, New York Times, 9 February 2021.

This is Ezra Klein interviewing Elizabeth Kolbert, author of The Sixth Extinction. She just wrote a book Under a White Sky: The Nature of the Future.. It’s about how we’ve altered nature so much, and are so trapped in relying on this, that there’s no way to go back to the good old days. At this point, any attempt to ‘go back’ amounts to going forward in another direction.

I’ll quote a bit:

Ezra Klein: Your book reads as an argument that we are past the point when we have the luxury of saying that things like geoengineering are off limits because we shouldn’t change the world that much. We’ve already changed it so much that the unthinkable now has to be thought.

Elizabeth Kolbert: I think that’s a reasonable interpretation. I think you could read it as, we are past the point of having that luxury. You could also read it as a species that has managed to muck up the atmosphere one way thinking about mucking up the atmosphere another way — what could possibly go wrong? I think those are both very valid readings.

Ezra Klein: You have a wonderful quote in the geoengineering chapter of your book from Andy Parker, who is a project director for the Solar Radiation Management Governance Initiative. He says, “We live in a world where deliberately dimming the [expletive] sun might be less risky than not doing it.” That feels like quite an indictment of the human race and where we’ve gotten ourselves to with all our knowledge and all our power.

Elizabeth Kolbert: I think that does sort of sum things up. We are in this very deep — there are only wrong answers, only hard choices at this point. Nothing easy from here on in.

Ezra Klein: What do you think of geoengineering?

Elizabeth Kolbert: I very consciously avoided coming down very clearly on that. But some very, very smart people are thinking about it and are very worried that it may be our best option at a certain point. And I think they may, unfortunately, be right — but wow, it’s dimming the [expletive] sun, you know?

Ezra Klein: I think how people feel about geoengineering depends on how they feel about the traditional political pathway. Do you think there is a significant chance that traditional politics are going to do enough to keep us under 2 degrees of warming?

Elizabeth Kolbert: Many, many scientists and many nations — especially the low-lying island nations that could disappear between here and 2 degrees — would say that’s really too high. So there’s a stretch goal, if you want, in the Paris accord of 1.5 degrees.

If you’re going to be honest about it, I think you have to say we’re basically at 1.5 degrees now. So that is not just a hard goal to reach; it’s getting to be almost geophysically impossible. Now, 2 degrees — presumably, it is still physically possible to do it.

Then that gets to the point you’re making: Is the world set up to do this? And the problem is not just that in the U.S. we are legislatively gridlocked — that, so far at least, we have been really incapable of taking significant action. And I do want to add, the U.S. is still the biggest single source of greenhouse gases that are up there in the atmosphere right now.

But then you have to look all around the world at all of the major players in this drama — China, which is now the single biggest emitter on an annual basis; the E.U., which is a very big emitter; India, which is increasingly a large emitter. So you have to ask, are we all going to get our act together?

Ezra Klein: One of the questions that I struggle with most in my own work right now is, what do you do if you believe that it is no longer politically plausible that normal politics will get to a reasonable outcome here? Sometimes I think about technological solutions — huge amounts of money being spent on not just renewables, but potentially studying things like geoengineering. Sometimes I wonder about things that are somewhere between political activism and extra-political. Where are you on this?

Elizabeth Kolbert: When we get into the “what could happen now owing to our failures,” that’s certainly where geoengineering comes in. A lot of very smart people are saying, look at the political system. It’s just not capable of moving fast enough. And the last 30 years are a pretty depressing proof of that.

And, as you say, you’re led either to a technofix or you’re led to a carbon dictatorship. I don’t know what you’re led to if you say, we just are incapable of moving fast enough under politics as they are. And the point, I think, that’s really important is on some level, it’s unknowable. How people will react all around the world, this is going to affect everyone. It’s going to affect some people much more brutally than others.

Applied Compositional Thinking for Engineers

Hey! There’s a new online course coming up!

• Applied Compositional Thinking for Engineers. January 7, 8, 11-15, 20-22, and 25-29. Taught by Andrea Censi, Jonathan Lorand and Gioele Zardini.

It’s not a coincidence that the acronym for “Compositional Thinking” is “CT”, just like “Category Theory”.

The course is free but registration is required. During the sign-up process you will be asked for the most convenient times for you; the instructors will choose what works best for a majority of participants. Each session will consist of short explanatory videos (to be watched in advance), and a 50 minute online lecture (allowing for questions and discussion).

Andrea Censi is known for his work on co-design. He and the others are at ETH Zürich, but this is not an official ETH Zürich course.

Here’s a video explaining the course:

Tropical Algebra and Railway Optimization

Simon Willerton pointed out a wonderful workshop, which unfortunately neither he nor I can attend… nor Jamie Vicary, who is at Birmingham:

• Tropical Mathematics & Optimisation for Railways, University of Birmingham, School of Engineering, Monday 18 June 2018.

If you can go, please do—and report back!

Tropical algebra involves the numbers made into a rig with minimization as the addition and addition as the multiplication. It’s called a rig because it’s a “ring without negatives”.

Tropical algebra is important in algebraic geometry, because if you take some polynomial equations and rewrite them replacing + with min and × with +, you get equations that describe shapes with flat pieces replacing curved surfaces, like this:

These simplified shapes are easier to deal with, but they shed light on the original curved ones! Click the picture for more on the subject from Johannes Rau.

Tropical algebra is also important for quantization, since classical mechanics chooses the path with minimum action while quantum mechanics sums over paths. But it’s also important for creating efficient railway time-tables, where you’re trying to minimize the total time it takes to get from one place to another. Finally these worlds are meeting!

Here’s the abstract, which shows that the reference to railway optimization is not just a joke:

Abstract. The main purpose of this workshop is to bring together specialists in tropical mathematics and mathematical optimisation applied in railway engineering and to foster further collaboration between them. It is inspired by some applications of tropical mathematics to the analysis of railway timetables. The most elementary of them is based on a controlled tropically linear dynamic system, which allows for a stability analysis of a regular timetable and can model the delay propagation. Tropical (max-plus) switching systems are one of the extensions of this elementary model. Tropical mathematics also provides appropriate mathematical language and tools for various other applications which willbe presented at the workshop.

The talks on mathematical optimisation in railway engineering will be given by Professor Clive Roberts and other prominent specialists working at the Birmingham Centre for Railway Research and Education (BCRRE). They will inform the workshop participants about the problems that are of actual interest for railways, and suggest efficient and practical methods of their solution.

For a glimpse of some of the category theory lurking in this subject, see:

• Simon Willerton, Project scheduling and copresheaves, The n-Category Café.

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.

Applied Category Theory 2018 – Videos

Some of the talks at Applied Category Theory 2018 were videotaped by the Statebox team. You can watch them on YouTube:

• David Spivak, A higher-order temporal logic for dynamical systems. Book available here and slides here.

• Fabio Zanasi and Bart Jacobs, Categories in Bayesian networks. Paper available here. (Some sound missing; when you hit silence skip forwards to about 15:00.)

• Bob Coecke and Aleks Kissinger, Causality. Paper available here.

• Samson Abramsky, Games and constraint satisfaction, Part 1 and Part 2. Paper available here.

• Dan Ghica, Diagrammatic semantics for digital circuits. Paper available here.

• Kathryn Hess, Towards a categorical approach to neuroscience.

• Tom Leinster, Biodiversity and the theory of magnitude. Papers available here and here.

• John Baez, Props in network theory. Slides available here, paper here and blog article here.

Props in Network Theory (Part 1)

Long before the invention of Feynman diagrams, engineers were using similar diagrams to reason about electrical circuits and more general networks containing mechanical, hydraulic, thermodynamic and chemical components. We can formalize this reasoning using ‘props’: a certain kind of categories whose objects are natural numbers, with the tensor product of objects given by addition. In this approach, each kind of network corresponds to a prop, and each network of this kind is a morphism in that prop. A network with inputs and outputs is a morphism from to Putting networks together in series is composition, and setting them side by side is tensoring.

In this paper, we study the props for various kinds of electrical circuits:

• John Baez, Brandon Coya and Franciscus Rebro, Props in network theory.

We start with circuits made solely of ideal perfectly conductive wires. Then we consider circuits with passive linear components like resistors, capacitors and inductors. Finally we turn on the power and consider circuits that also have voltage and current sources.

And here’s the cool part: each kind of circuit corresponds to a prop that pure mathematicians would eventually invent on their own! So, what’s good for engineers is often mathematically natural too.

We describe the ‘behavior’ of these various kinds of circuits using morphisms between props. In particular, we give a new proof of the black-boxing theorem proved earlier with Brendan Fong. Unlike the original proof, this new one easily generalizes to circuits with nonlinear components! We also use a morphism of props to clarify the relation between circuit diagrams and the signal-flow diagrams in control theory.

Here’s a quick sketch of the main ideas.

Props in network theory

In his 1963 thesis, Lawvere introduced functorial semantics: the use of categories with specified extra structure as ‘theories’ whose ‘models’ are structure-preserving functors into other such categories:

• F. W. Lawvere, Functorial semantics of algebraic theories, Ph.D. thesis, Department of Mathematics, Columbia University, 1963. Also in Reprints in Theory and Applications of Categories 5 (2003), 1–121.

In particular, a Lawvere theory is a category with finite cartesian products and a distinguished object such that every object is a power These can serve as theories of mathematical structures that are sets equipped with -ary operations

obeying equational laws. However, structures of a more linear-algebraic nature are often vector spaces equipped with operations of the form

To extend functorial semantics to these, Mac Lane introduced props—or as he called them, ‘PROPs’. The acronym stands for ‘products and permutations’:

• Saunders Mac Lane, Categorical algebra, Bulletin of the American Mathematical Society 71 (1965), 40–106.

A prop is a symmetric monoidal category equipped with a distinguished object such that every object is a tensor power Working with tensor products rather than cartesian products puts operations having multiple outputs on an equal footing with operations having multiple inputs.

Already in 1949 Feynman had introduced his famous diagrams, which he used to describe theories of elementary particles. For a theory with just one type of particle, Feynman’s method amounts to specifying a prop where an operation describes a process with particles coming in and going out. Although Feynman diagrams quickly caught on in physics, only in the 1980s did it become clear that they were a method of depicting morphisms in symmetric monoidal categories. A key step was the work of Joyal and Street, which rigorously justified reasoning in any symmetric monoidal category using ‘string diagrams’—a generalization of Feynman diagrams:

• André Joyal and Ross Street, The geometry of tensor calculus I, Advances in Mathematics 88 (1991), 55–112.

By now, many mathematical physicists are aware of props and the general idea of functorial semantics. In constrast, props seem to be virtually unknown in engineering!

But engineers have been using diagrammatic methods ever since the rise of electrical circuits. And in the 1940s, Olson explained how to apply circuit diagrams to networks of mechanical, hydraulic, thermodynamic and chemical components:

• Harry F. Olson, Dynamical Analogies, Van Nostrand, New York, 1943.

By 1961, Paynter had made the analogies between these various systems mathematically precise using ‘bond graphs’:

• Henry M. Paynter, Analysis and Design of Engineering Systems, MIT Press, Cambridge, Massachusetts, 1961.

Here he shows a picture of a hydroelectric power plant, and the bond graph that abstractly describes it:

By 1963, Forrester was using circuit diagrams in economics:

• Jay Wright Forrester, Industrial Dynamics, MIT Press, Cambridge, Massachusetts, 1961.

In 1984, Odum published a beautiful and influential book on their use in biology and ecology:

• Howard T. Odum, Ecological and General Systems: An Introduction to Systems Ecology, Wiley, New York, 1984.

We can use props to study circuit diagrams of all these kinds! The underlying mathematics is similar in each case, so we focus on just one example: electrical circuits. For other examples, take a look at this:

• John Baez, Network theory (part 29), Azimuth, 23 April 2013.

In our new paper, we illustrate the usefulness of props by giving a new, shorter proof of the ‘black-boxing theorem’ proved here:

• John Baez and Brendan Fong, A compositional framework for passive linear networks. (Blog article here.)

A ‘black box’ 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 a process called ‘black-boxing’, which forgets its inner workings and records only the relation it imposes between its inputs and outputs. Systems with inputs and outputs can be seen as morphisms in a category, where composition uses the outputs of the one system as the inputs of another. We thus expect black-boxing to be a functor out of a category of this sort. A ‘black-boxing theorem’ makes this intuition precise.

In an electrical circuit, associated to each wire there is a pair of variables called the potential and current When we black-box such a circuit, we record only the relation it imposes between the variables on its input and output wires. Since these variables come in pairs, this is a relation between even-dimensional vector spaces. But these vector spaces turn out to be equipped with extra structure: they are symplectic vector spaces, meaning they are equipped with a nondegenerate antisymmetric bilinear form. Black-boxing gives a relation that respects this extra structure: it is a ‘Lagrangian’ relation.

Why does symplectic geometry show up when we black-box an electrical circuit? The first proof of the black-boxing theorem answered this question. A circuit made of linear resistors acts to minimize the total power dissipated in the form of heat. More generally, any circuit made of linear resistors, inductors and capacitors obeys a generalization of this ‘principle of minimum power’. Whenever a system obeys a minimum principle, it establishes a Lagrangian relation between input and output variables. This fact was first noticed in classical mechanics, where systems obey the ‘principle of least action’. Indeed, symplectic geometry has its origins in classical mechanics. But it applies more generally: for any sort of system governed by a minimum principle, black-boxing should give a functor to some category where the morphisms are Lagrangian relations.

The first step toward such a theorem for electrical circuits is to treat circuits as morphisms in a suitable category. We start with circuits made only of ideal perfectly conductive wires. These are morphisms in a prop we call defined in Section 3 of our paper. In Section 8 we construct a black-boxing functor

sending each such circuit to the relation it defines between its input and output potentials and currents. Here is a prop with symplectic vector spaces of the form as objects and linear Lagrangian relations as morphisms, and is a morphism of props. We work in a purely algebraic fashion, so here can be any field.

In Section 9 we extend black-boxing to a larger class of circuits that include linear resistors, inductors and capacitors. This gives a new proof of the black-boxing theorem that Brendan and I proved: namely, there is a morphism of props

sending each such linear circuit to the Lagrangian relation it defines between its input and output potentials and currents. The ease with which we can extend the black-boxing functor is due to the fact that all our categories with circuits as morphisms are props. We can describe these props using generators and relations, so that constructing a black-boxing functor simply requires that we choose where it sends each generator, and check that the all the relations hold. In Section 10 we explain how electric circuits are related to signal-flow diagrams, used in control theory. Finally, in Section 11, we illustrate how props can be used to study nonlinear circuits.

Outline of the results

The paper is pretty long, so here’s a more detailed outline of the results.

In Section 1 we explain a general notion of `-circuit’ that was first introduced under a different name here:

• R. Rosebrugh, N. Sabadini and R. F. C. Walters, Generic commutative separable algebras and cospans of graphs, Theory and Applications of Categories 15 (2005), 164–177.

An -circuit is a cospan of finite sets where the apex is the set of nodes of a graph whose edges are labelled by elements of some set In applications to electrical engineering, the elements of describe different ‘circuit elements’ such as resistors, inductors and capacitors. We discuss a symmetric monoidal category whose objects are finite sets and whose morphisms are (isomorphism classes of) -circuits.

In Section 2 we study when is a 1-element set. We call this category simply In applications to engineering, a morphism in describes circuit made solely of ideal conductive wires. We show how such a circuit can be simplified in two successive stages, described by symmetric monoidal functors:

Here is the category of cospans of finite sets, while is the category of ‘corelations’ between finite sets. Corelations, categorically dual to relations, are already known to play an important role in network theory:

• Brendan Fong, Decorated corelations.

Just as a relation can be seen as a jointly monic span, a corelation can be seen as a jointly epic cospan. The functor crushes any graph down to its set of components, while reduces any cospan to a jointly epic one.

In Section 4 we turn to props. Propositions 11 and 12, proved in Appendix A.1 with the help of Steve Lack, characterize which symmetric monoidal categories are equivalent to props and which symmetric monoidal functors are isomorphic to morphisms of props. We use these to find props equivalent to and This lets us reinterpret the arrows here as morphisms of props:

In Section 5 we discuss presentations of props. Proposition 19, proved in Appendix A.2 using a result of Todd Trimble, shows that the category of props is monadic over the category of signatures, This lets us work with props using generators and relations. We conclude by recalling a presentation of due to Lack and a presentation of due to Coya and Fong:

• Steve Lack, Composing PROPs, Theory and Applications of Categories 13 (2004), 147–163.

• Brandon Coya and Brendan Fong, Corelations are the prop for extraspecial commutative Frobenius monoids, Theory and Applications of Categories 32 (2017), 380–395. (Blog article here.)

In Section 6 we introduce the prop This prop is equivalent to the symmetric monoidal category with finite-dimensional vector spaces over the field as objects and linear relations as morphisms, with direct sum as its tensor product. A presentation of this prop was given in these papers:

• Filippo Bonchi, Pawel Sobociénski and Fabio Zanasi, Interacting Hopf algebras, Journal of Pure and Applied Algebra 221 (2017), 144–184.

• John Baez and Jason Erbele, Categories in control, Theory and Application of Categories 30 (2015), 836–881. (Blog article here.)

In Section 7 we state the main result in the paper by Rosebrugh, Sabadini and Walters. This gives a presentation of Equivalently, it says that is the coproduct, in the category of props, of and the free prop on a set of unary operations, one for each element of This result makes it easy to construct morphisms from to other props.

In Section 8 we introduce the prop where morphisms are Lagrangian linear relations between symplectic vector spaces, and we construct the black-boxing functor Mathematically, this functor is the composite

where is a symmetric monoidal functor defined by its action on the generators of In applications to electrical engineering, the black-boxing functor maps any circuit of ideal conductive wires to its ‘behavior’: that is, to the relation that it imposes on the potentials and currents at its inputs and outputs.

In Section 9 we extend the black-boxing functor to circuits that include resistors, inductors, capacitors and certain other linear circuit elements. The most elegant prop having such circuits as morphisms is meaning with the label set taken to be a field $k.$ We characterize the black-boxing functor

in Theorem 41.

In Section 10 we expand the scope of inquiry to include ‘signal-flow diagrams’, which are important in control theory. We explain how signal-flow diagrams serve as a syntax for linear relations. Concretely, this means that signal-flow diagrams are morphisms in a free prop with the same generators as but no relations. There is thus a morphism of props

mapping any signal-flow diagrams to the linear relation that it denotes. It is natural to wonder how this is related to the black-boxing functor

The answer involves the free prop which arises when we take the simplest presentation of and omit the relations. This comes with a map

which reinstates those relations, and in Theorem 44 we show there is a map of props making this diagram commute:

Putting everything together, we get this grand commuting diagram relating circuit diagrams, linear circuits, signal flow diagrams, cospans, corelations, Lagrangian relations, and linear relations:

Finally, in Section 11 we illustrate how props can also be used to study nonlinear circuits. Namely, we show how to include voltage and current sources. Black-boxing these gives Lagrangian affine relations between symplectic vector spaces! Eventually we’ll get around to studying more general nonlinear circuits… but not today.

For more, see:

• Props in network theory (part 2).

Applied Category Theory at NIST (Part 1)

I think it’s really cool how applied category theory is catching on. My former student Blake Pollard is working at the National Institute of Standards and Technology on applications of category theory to electrical engineering. He’s working with Spencer Breiner… and now Breiner is helping run a workshop on this stuff:

• Applied Category Theory: Bridging Theory & Practice, March 15–16, 2018, NIST, Gaithersburg, Maryland, USA. Organized by Spencer Breiner and Eswaran Subrahmanian.

It’s by invitation only, but I can’t resist mentioning its existence. Here’s the idea:

What: The Information Technology Laboratory at NIST is pleased to announce a workshop on Applied Category Theory to be held at NIST’s Gaithersburg, Maryland campus on March 15 & 16, 2018. The meeting will focus on practical avenues for introducing methods from category theory into real-world applications, with an emphasis on examples rather than theorems.

Who: The workshop aims to bring together two distinct groups. First, category theorists interested in pursuing applications outside of the usual mathematical fields. Second, domain experts and research managers from industry, government, science and engineering who have in mind potential domain applications for categorical methods.

Intended Outcomes: A proposed landscape of potential CT applications and the infrastructure needed to realize them, together with a 5-10 year roadmap for developing the field of applied category theory. This should include perspectives from industry, academia and government as well as major milestones, potential funding sources, avenues for technology transfer and necessary improvements in tool support and methodology. Exploratory collaborations between category theorists and domain experts. We will ask that each group come prepared to meet the other side. Mathematicians should be prepared with concrete examples that demonstrate practical applications of CT in an intuitive way. Domain experts should bring to the table specific problems to which they can devote time and/or funding as well as some reasons about why they think CT might be relevant to this application.

Invited Speakers:
John Baez (University of California at Riverside) and John Foley (Metron Scientific Solutions).
Bob Coecke (University of Oxford).
Dusko Pavlovic (University of Hawaii).

Some other likely participants include Chris Boner (Metron), Arquimedes Canedo (Siemens at Princeton), Stephane Dugowson (Supméca), William Edmonson (North Carolina A&T), Brendan Fong (MIT), Mark Fuge (University of Maryland), Jack Gray (Penumbra), Helle Hansen (Delft), Jelle Herold (Statebox), Marisa Hughes (Johns Hopkins), Steve Huntsman (BAE Systems), Patrick Johnson (Dassault Systèmes), Al Jones (NIST), Cliff Joslyn (Pacific Northwest National Laboratory), Richard Malek (NSF), Tom Mifflin (Metron), Ira Monarch (Carnegie Mellon), John Paschkewitz (DARPA), Evan Patterson (Stanford), Blake Pollard (NIST), Emilie Purvine (Pacific Northwest National Laboratory), Mark Raugas (Pacific Northwest National Laboratory), Bill Regli (University of Maryland), Michael Robinson (American U.) Alberto Speranzon (Honeywell Aerospace), David Spivak (MIT), Eswaran Subrahmanian (Carnegie Mellon), Jamie Vicary (Birmingham and Oxford), and Ryan Wisnesky (Categorical Informatics).

A bunch of us will stay on into the weekend and talk some more. I hope we make a lot of progress—and I plan to let you know how it goes!

I’ll be giving a joint talk with John Foley about our work using operads to design networks. This work is part of the Complex Adaptive System Composition and Design Environment project being done by Metron Scientific Solutions and managed by John Paschkewitz at DARPA.