## Compositionality in Network Theory

I gave a talk at the workshop on compositionality at the Simons Institute for the Theory of Computing next week. I spoke about some new work with Blake Pollard. You can see the slides here:

• John Baez, Compositionality in network theory, 6 December 2016.

and a video here:

Abstract. To describe systems composed of interacting parts, scientists and engineers draw diagrams of networks: flow charts, Petri nets, electrical circuit diagrams, signal-flow graphs, chemical reaction networks, Feynman diagrams and the like. In principle all these different diagrams fit into a common framework: the mathematics of symmetric monoidal categories. This has been known for some time. However, the details are more challenging, and ultimately more rewarding, than this basic insight. Two complementary approaches are presentations of symmetric monoidal categories using generators and relations (which are more algebraic in flavor) and decorated cospan categories (which are more geometrical). In this talk we focus on the latter.

This talk assumes considerable familiarity with category theory. For a much gentler talk on the same theme, see:

### 11 Responses to Compositionality in Network Theory

1. I just spent an hour going through the slides and found them very understandable. The top-prio thing I needed to postpone is working through examples of what exactly the pushouts do when the functions i and o are not bijective.

• John Baez says:

In the category of sets, when we compose cospans:

the set $\Gamma +_Y \Gamma'$ is a pushout. (Pardon the weird notation $\Gamma$ for a set; I’m just reusing a diagram I had sitting around.) This pushout turns out to work as follows: first take the disjoint union of the sets $\Gamma$ and $\Gamma'$, and then mod out by the smallest equivalence relation such that $o(y) \sim i'(y)$ for all $y \in Y$. This is particularly simple when $o$ and $i'$ are injective, but it’s true in general.

• Thanks for the clarification! Allowing non-injective i and o is the least intuitive part for me. Does this come from a practical need, or does one do this just because one can? Is there perchance a symmetric monoidal subcategory of cospans with injective i and o that would also do the job in realistic cases?

• John Baez says:

A good general rule in mathematics is “don’t disallow something unless you need to”. So, demanding that $i$ and $o$ be injective is not something you should do unless (or until) you can prove something interesting that requires this assumption.

More importantly, non-injective $i$ and $o$ are required to get these cospan categories to be compact closed. I noticed this a long time ago when working on circuits made of resistors.

Also, to get identity morphisms we need cospans where the range of $i$ is not disjoint from the range of $o$. So, we definitely don’t want to demand that their ranges be disjoint!

• Compact closure, of course, that’s a strong argument!

I’ve reflected why I asked my injectivity question, and I’ve realized the source was my inner software engineer: I have an unusual synesthesia that makes me constantly see analogies between computer code and mathematical theories. When faced with the pushout, I instinctively viewed it as an algorithm in a computer-algebra software I might write and have to maintain. So the question surfaced: am I willing to implement and maintain the more complicated pushout? I find it interesting how the “don’t disallow” you mention turns into an “be careful before you add” when one switches from the mathematical to the algorithmic or software maintenance perspective.

Anyway, your compact closure argument makes moot any point I might have had.

• John Baez says:

Carsten wrote:

So the question surfaced: am I willing to implement and maintain the more complicated pushout? I find it interesting how the “don’t disallow” you mention turns into an “be careful before you add” when one switches from the mathematical to the algorithmic or software maintenance perspective.

Yes, interesting! I’m glad to hear that you can explain reason for wanting to disallow noninjective legs on your cospan. If you’re maintaing software this might make sense. What really bugs me is pure mathematicians who throw unnecessary axioms into their theories just because those axioms hold in some paradigmatic example of what they’re thinking about, without carefully investigating what those axioms help us prove. Poorly thought-out axioms that disallow certain objects or morphisms in a category often make that category worse—they actually prevent us from proving interesting results.

A classic example is demanding that some set be nonempty just because the empty set is a bit spooky. Of course the empty examples aren’t the ones we have in mind, but throwing out the empty set tends to throw out initial objects and thus prevent a category from having all colimits.

2. John Baez says:

By the way, I updated the talk slides so that now the penultimate slide shows lots of different symmetric monoidal categories of networks.

3. Here at the Simons Institute, my talk on compositionality in network theory introduced ‘decorated cospans’ as a general model of open systems. These were invented by Brendan Fong, and are nicely explained in his thesis:

• Brendan Fong, The Algebra of Open and Interconnected Systems.

But he went further: to understand the externally observable behavior of an open system we often want to simplify a decorated cospan and get another sort of structure, which he calls a ‘decorated corelation’. His talk here explains decorated corelations and what they’re good for:

4. Armin Reichert says:

Monoidal categories (x-categories) and their graphical representation (logic-topological nets) have been introduced in 1965 by Prof. Günter Hotz from the University in Saarbrücken, Germany.

They have been used in circuit design and formal language theory from that time on, the theory has been generalized later to bicategories and been used as the mathematical foundation of the CADIC VLSI design system.

• John Baez says:

Interesting! Of course the usual story is that monoidal categories (with associators obeying the pentagon identites, etc.) were introduced by Mac Lane here:

• Saunders Mac Lane, Natural associativity and commutativity, Rice Univ. Studies, 49 (1963), 28–46.

Did Hotz refer to Mac Lane’s work, or did he think of his ideas independently?

• Armin Reichert says:

Unfortunately I don’t own my copies of Hotz’s papers anymore.

In this one (in German):

G. Hotz. Eine Algebraisierung des Syntheseproblems für Schaltkreise. EIK Journal of Information Processing and Cybernetics, 1:185-205,209-231, 1965.

the theory of free x-categories has been introduced together with a “logic-topological” representation of the morphisms by planar nets.

I am almost sure that Hotz at that time already knew about the work of Eilenberg & Mac Lane on category theory.

My comment referred more to the “net calculus” which gave these diagrams and their composition (later also their hierarchical definition) a precise algebraic meaning and also introduced the concept of functorial semantics for these networks.

In the paper

G. Hotz. Eindeutigkeit und Mehrdeutigkeit formaler Sprachen. EIK Journal of Information Processing and Cybernetics, 2:235-246, 1966

the concept was applied to Chomsky languages thus providing an algebraic foundation for the theory of formal languages. This for example provided an algebraic description of “derivations” in Chomsky grammars and layed the foundation for handling formal language theory in a category-theoretic setting.

Regards
Armin

This site uses Akismet to reduce spam. Learn how your comment data is processed.