Matteo Capucci, Jade Master, and I were discussing ways to define hybrid systems formed by decorating Petri nets with systems at their places at the recent ARIA meeting, and in the course of this we came up with a notion of “foam diagram” that I would like to describe here.
Bubble diagrams
First, let me describe what I like to call “bubble diagrams” (or, sometimes, “rhizomes” or “forgotten potato diagrams”), which are a special sort of cospan diagram.
Definition: The operad (or multicategory) of bubble diagrams has objects the finite sets (where we consider a finite set B as a bubble with |B| ports or wires sticking out of them), with an op C : \mathsf{Bubble}(B_1, \ldots, B_n; A) being a cospan B_1 + \cdots + B_n \twoheadrightarrow C \hookleftarrow A with left leg a surjection and right leg an injection. I call the elements of C “connections”.
These can be drawn as diagrams where we put the bubbles B_1 through B_n inside the bubble A and then draw C dots in A outside the B_i; then we draw a map from every port in B_i or A to the corresponding dot from C given by the image of maps in the span. This is just as Fong and Spivak do in their paper on hypergraph categories. However, the extra restrictions mean that
- Every outer port connects to a unique connection, and
- Every connection connects to some inner port.
In particular, all outer ports will be live — they are connected to some inner ports — and there are no “passing wires” — outer ports can only be connected to inner ports, but not to eachother.
Bubble diagrams give the pure expression of variable sharing. We think of the bubbles as exposing variables on their ports, while the surjection B_1 + \cdots + B_n \twoheadrightarrow C gives a corelation amongst these variables, clustering them into blocks that we will set equal (or “share”), while the injection C \hookleftarrow A chooses some of these variables to re-expose on the ports of A.
In particular, the monoidal category of such cospans with coproduct as the monoidal structure can be presented as the PROP freely generated by an associative binary operation \mathsf{share} : 2 \to 1 and a co-nullary \mathsf{hide} : 1 \to 0. As cospans, these are \{0, 1\} \twoheadrightarrow \{1\} \hookleftarrow \{1\} and \{1\} \twoheadrightarrow \{1\} \hookleftarrow \emptyset; it’s not so hard to show that all such cospans are given as composites of these.
Another thing to note about these cospans is that their double category (that is, the usual double category of cospans, but restricted to those whose left leg is surjective and right leg is injective) is thin and span-ish — that is, the covariant Pare representable double functors are pseudo. The first follows from the fact that the left leg is epi; the second from the adhesivity of finite sets. This double nature is important for systems theory, but I won’t go into it here.
Bubble diagrams come up in variable sharing systems theories — as in Willems’ behavioral approach to control theory — and in port-plugging systems theories — as in theories arising from decorated or structure cospan constructions. See Chapter 6 of my book for more details on this.
(Just to note: for the purposes of this blog post, we don’t really need the left leg to be surjective. But we do need the right leg to be injective!)
Foam Diagrams
Suppose that we have theory of system diagrams with exposed ports — for example, as arising out of a decorated or structured cospan construction. Then we will have an algebra of the operad of bubble diagrams. (To get morphisms of systems we really need to work double categorically, but I’m eliding that in this post. Last I’ll mention it!)
Intuitively, we may fill a bubble B with a system that exposes B ports; we may then compose systems using a bubble diagram by gluing together the ports in the inverse image of c \in C of the sharing map B_1 + \cdots + B_n \twoheadrightarrow C; we then expose those ports of the of the combined system which are pointed to by C \hookleftarrow A.
For example, we might take pairs (G, \partial : B \hookrightarrow G) of a graph G and an choice of B-many nodes in B to be our sort of system; we can them compose (G_1, \partial : B_1 \hookrightarrow G_1), \ldots, (G_n, \partial : B_n \hookrightarrow G_n) along the bubble diagram B_1 + \ldots + B_n \twoheadrightarrow C \hookleftarrow A by defining C_{\ast}(G_1, \ldots, G_n) to be the pushout
in the category of graphs, where we consider finite sets as discrete (edgeless) graphs. We define the boundary of the composed map as in the above diagram as well. Clearly this sort of thing will work with essentially any systems arising from decorated cospan constructions.
Now very often the parts of the diagram that could be exposed as ports represent “places” of some sort — in the above example, they are nodes in a graph and so “places” in that sense. We often glue Petri nets together by equating their places. These places might have local structure — we might imagine that there is an entire dynamical system happening inside the place, for example. As a very simple case, suppose we weight our graphs with a number at each node: w : G_0 \to \mathbb{N}.
When we glue together such diagrams-with-local-structure, we must also figure out how to combine that local structure. One way would be to only allow us to compose two such diagrams when we have the same structure at each place we are gluing together; in the above example, this would mean only letting us glue together two graphs along a node when that node had the same weight in each graph. However, we might want to instead combine the local structure somehow; for example, by adding the weights.
Where the port-plugging composition is governed by bubble diagrams, this new kind of composition will be governed by foam diagrams — the idea being that these are like bubble diagrams but themselves made up of dense little bubbles of a qualitatively different sort (giving a “foam”).
Suppose that our local structure is itself an algebra \mathcal{A} : \mathbb{I} \to \mathsf{Set} for some symmetric operad \mathbb{I} (of “local interfaces”). We will create an operad \mathsf{Foam}(\mathbb{I}), so that diagrams locally structured by \mathcal{A} are algebras for \mathsf{Foam}(\mathbb{I}). This is very similar to a sort of “\mathsf{Fam}-construction”.
Definition: Let \mathbb{I} be a symmetric operad. Define the operad \mathsf{Foam}(\mathbb{I}) to have objects (B \in \mathsf{Fin},\, I \in \mathsf{ob}\mathbb{I}^B) pairs of a bubble B with ports labelled by interfaces (objects of \mathbb{I}). Then \mathsf{Foam}(\mathbb{I})((B_1, I_1), \ldots, (B_n, I_n); (A, J)) consists of a bubble diagram B_1 + \cdots + B_n \overset{\sigma}{\twoheadrightarrow} C \hookleftarrow A together with K \in \mathsf{ob}\mathbb{I}^C such that K|_A = J and, for every c \in C, a “composition pattern” p_c \in \mathbb{I}((I_b)_{\sigma(b) = c}; K_c). These compose by composing the bubble diagrams and by labelling the induced connections by the composite of the appropriate “composition patterns” in \mathbb{I}.
Drawing this is quite fun: we draw the bubble diagram, and at each port we put an interface from \mathbb{I} and at every connection we put a composition pattern (e.g. a wiring diagram of some sort) whose inner interfaces are those of the inner ports wired to that connection; if that connection is wired to an outer port, then the outer port is labeled by the outer interface of the composition pattern on that connection. When you compose them, you end up joining a bunch of inner connections into a single outer connection; you then compose their labels operadically in \mathbb{I}.
The above example of weighted graphs is built from seeing the additive monoid of the naturals \mathbb{N} : 1 \to \mathsf{Set} as an algebra for the terminal symmetric operad, and then forming \mathsf{Foam}(1) — which turns out to just be \mathsf{Bubble} again, but we did pick an overly simple example.
A better example would be to label each node by a Moore machine; when we glue nodes together we would have to choose how to wire up their associated Moore machines. This would be an algebra for \mathsf{Foam}(\mathsf{Lens}(\mathsf{Arity})), where \mathsf{Lens}(\mathsf{Arity}) is the operad of lens-based wiring diagrams.
Where are we going with this?
We can do this whole story double-theoretically, which lets us keep track of morphisms between systems as well. With that in mind, we hope to be able to hybridize a doctrine with the port-plugging doctrine that composes via bubble diagrams, to get a good notion of “hybrid system that is some kind of graph-like structure with dynamical systems hanging out at every place”. We then hope to show that in good cases, we can represent processes that move through the “space” of the graph-like structure while flowing in each internal place as maps out of particularly simple hybrid systems. By the general machinery in Chapter 5 of my book, this would give us a series of compositionality theorems for hybrid systems.
There’s a lot of stuff to work out precisely here — in particular, how to handle the notion of “guards” that are so ubiquitous in notions of hybrid system. Hopefully they can be baked into the objects of \mathbb{I}, but it isn’t so clear to me how this will end up working.
Toby Smithe has been talking about “spatial systems theory” a bit recently — is this related?