Theory and Applications of Categories, Vol. 30, No. 51, 2015, pp. 1793–1822.

ALGEBRAS OF OPEN DYNAMICAL SYSTEMS ON THE OPERAD OF WIRING DIAGRAMS

DMITRY VAGNER, DAVID I. SPIVAK, AND EUGENE LERMAN

Abstract. In this paper, we use the language of operads to study open dynamical systems. More specifically, we study the algebraic nature of assembling complex dynamical systems from an interconnection of simpler ones. The syntactic architecture of such interconnections is encoded using the visual language of wiring diagrams. We define the symmetric monoidal category W, from which we may construct an operad OW, whose objects are black boxes with input and output ports, and whose morphisms are wiring diagrams, thus prescribing the algebraic rules for interconnection. We then define two W-algebras G and L, which associate semantic content to the structures in W. Respectively, they correspond to general and to linear systems of differential equations, in which an internal state is controlled by inputs and produces outputs. As an example, we use these algebras to formalize the classical problem of systems of tanks interconnected by pipes, and hence make explicit the algebraic relationships among systems at different levels of granularity.

1. Introduction

It is widely believed that complex systems of interest in the sciences and engineering are both modular and hierarchical. Network theory uses the tools and visual language of graph theory to model such systems, and has proven to be both effective and flexible in describing their modular character. However, the field has put less of an emphasis on finding powerful and versatile language for describing the hierarchical aspects of complex systems. There is growing confidence that category theory can provide the necessary conceptual setting for this project. This is seen, for example, in Mikhail Gromov’s wellknown claim, “the mathematical language developed by the end of the 20th century by far exceeds in its expressive power anything, even imaginable, say, before 1960. Any meaningful idea coming from science can be fully developed in this language.” [Gro13]

Joyal and Street’s work on string diagrams [JS91] for monoidal categories and (with Verity) on traced monoidal categories [JSV96] has been used for decades to visualize compositions and feedback in networked systems, for example in the theory of flow charts [AMMO10]. Precursors, such as Penrose diagrams and flow diagrams, have been used in physics and the theory of computation, respectively, since the 1970’s [Sco71, BS11].

Spivak was supported by ONR grant N000141310260 and AFOSR grant FA9550-14-1-0031. Received by the editors 2015-02-10 and, in revised form, 2015-11-17. Transmitted by Kathryn Hess. Published on 2015-12-03. 2010 Mathematics Subject Classification: 93A13. Key words and phrases: Operads, Monoidal Categories, Wiring Diagrams, Dynamical Systems. \begin{matrix}c \\ ◯ \end{matrix} Dmitry Vagner, David I. Spivak, and Eugene Lerman, 2015. Permission to copy for private use

granted.

Over the past several years, the second author and collaborators have been developing a novel approach to modular hierarchical systems based on the language of operads and symmetric monoidal categories [Spi13, SR13]. The main contribution to the theory of string diagrams of the present research program is the inclusion of an outer box, which allows for holarchic [Koe67] combinations of these diagrams. That is, the parts can be assembled into a whole, which can itself be a part. The composition of such assemblies can now be viewed as morphism composition in an operad. In fact, there is a strong connection between traced monoidal categories and algebras on these operads, such as our operad OW of wiring diagrams, though it will not be explained here (see [SSR15] for details).

More broadly, category theory can organize graphical languages found in a variety of applied contexts. For example, it is demonstrated in [BS11] and [Coe13] that the theory of monoidal categories unifies the diagrams coming from diverse fields such as physics, topology, logic, computation, and linguistics. More recently, as in [BB12], there has been growing interest in viewing more traditionally applied fields, such as ecology, biology, chemistry, electrical engineering, and control theory through such a lens. Specifically, category theory has been used to draw connections among visual languages such as planar knot diagrams, Feynman diagrams, circuit diagrams, signal flow graphs, Petri nets, entity relationship diagrams, social networks, and flow charts. This research is building toward what John Baez has called “a foundation of applied mathematics” [Bae13].

The goal of the present paper is to show that open continuous time dynamical systems form an algebra over a certain (colored) operad, which we call the operad of wiring diagrams. It is a variant of the operad that appeared in [SR13]. That is, wiring diagrams provide a straightforward, diagrammatic language to understand how dynamical systems that describe processes can be built up from the systems that describe its sub-processes.

More precisely, we will define a symmetric monoidal category W of black boxes and wiring diagrams. Its underlying operad OW is a graphical language for building larger black boxes out of an interconnected set of smaller ones. We then define two W-algebras, G and L, which encode open dynamical systems, i.e., differential equations of the form

\begin{cases}Q̇ = f^{in}(Q, input) \\ output = f^{out}(Q) \end{cases}  (1)

where Q represents an internal state vector, Q̇ = \frac{dQ}{dt} represents its time derivative, and input and output represent inputs to and outputs from the system. In G, the functions f^{in} and f^{out} are smooth, whereas in the subalgebra L ⊆ G, they are moreover linear. The fact that G and L are W-algebras captures the fact that these systems are closed under wiring diagram interconnection.

Our notion of interconnection is a generalization of that in Deville and Lerman [DL10], [DL15], [DL]. Their version of interconnection produces a closed system from open ones, and can be understood in the present context as a morphism whose codomain is the closed box (see Definition 3.8). Graph fibrations between wiring diagrams form an important part of their formalism, though we do not discuss that aspect here.

This paper is the third in a series, following [SR13] and [Spi13], on using wiring diagrams to model interactions. The algebra we present here, that of open systems, is distinct from the algebras of relations and of propagators studied in earlier works. Beyond the dichotomy of discrete vs. continuous, these algebras are markedly different in structure. For one thing, the internal wires in [SR13] themselves carry state, whereas here, a wire should be thought of as instantaneously transmitting its contents from an output site to an input site. Another difference between our algebra and those of previous works is that the algebras here involve open systems in which, as in (1), the instantaneous change of state is a function of the current state and the input, whereas the output depends only on the current state (see Definition 4.2). The differences between these algebras is also reflected in a mild difference between the operad we use here and the one used in previous work.

1.1. Motivating example. The motivating example for the algebras in this paper comes from classical differential equations pedagogy; namely, systems of tanks containing salt water concentrations, with pipes carrying fluid among them. The systems of ODEs produced by such applications constitute a subset of those our language can address; they are linear systems with a certain form (see Example 5.7). To ground the discussion, we consider a specific example.

1.2. Example. Figure 1 below reimagines a problem from Boyce and DiPrima’s canonical text [BD65, Figure 7.1.6] as a dynamical system over a wiring diagram.

Y Y_{a}^{in} Y_{b}^{in} Y_{a}^{out} X_{1} Q_{1}(t) oz salt 30 gal water X_{1a}^{in} X_{1b}^{in} X_{1a}^{out} X_{2} Q_{2}(t) oz salt 20 gal water X_{2a}^{in} X_{2b}^{in} X_{2a}^{out} X_{2b}^{out} 3 gal/min 1.5 gal/min 1 oz/gal 1 gal/min 3 oz/gal 2.5 gal/min 1.5 gal/min

Figure 1: A dynamical system from Boyce and DiPrima interpreted over a wiring diagram Φ: X_{1}, X_{2} → Y in OW.

In this diagram, X_{1} and X_{2} are boxes that represent tanks consisting of salt water solution. The functions Q_{1}(t) and Q_{2}(t) represent the amount of salt (in ounces) found in 30 and 20 gallons of water, respectively. These tanks are interconnected with each other by pipes embedded within a total system Y. The prescription for how wires are attached among the boxes is formally encoded in the wiring diagram Φ: X_{1}, X_{2} → Y, as we will discuss in Definition 3.1.

Both tanks are being fed salt water concentrations at constant rates from the outside world. Specifically, X_{1} is fed a 1 ounce salt per gallon water solution at 1.5 gallons per minute and X_{2} is fed a 3 ounce salt per gallon water solution at 1 gallon per minute. The tanks also both feed each other their solutions, with X_{1} feeding X_{2} at 3 gallons per minute and X_{2} feeding X_{1} at 1.5 gallons per minute. Finally, X_{2} feeds the outside world its solution at 2.5 gallons per minute.

The dynamics of the salt water concentrations both within and leaving each tank X_{i} is encoded in a linear open system f_{i}, consisting of a differential equation for Q_{i} and a readout map for each X_{i} output (see Definition 2.13). Our algebra L allows one to assign a linear open system f_{i} to each tank X_{i}, and by functoriality the morphism Φ: X_{1}, X_{2} → Y produces a linear open system for the larger box Y. We will explore this construction in detail, in particular providing explicit formulas for it in the linear case, as well as for more general systems of ODEs.

Acknowledgments. We thank the anonymous referee for helping us improve the paper.

2. Preliminary Notions

Throughout this paper we use the language of monoidal categories and functors. Depending on the audience, appropriate background on basic category theory can be found in MacLane [ML98], Awodey [Awo10], or Spivak [Spi14]. Leinster [Lei04] is a good source for more specific information on monoidal categories and operads. We refer the reader to [KFA69] for an introduction to dynamical systems.

2.1. Notation. We denote the category of sets and functions by Set and the full subcategory spanned by finite sets as FinSet. We generally do not concern ourselves with cardinality issues. We follow Leinster [Lei04] and use × for binary product and Π for arbitrary product, and dually + for binary coproduct and ⨿ for arbitrary coproduct in any category. By operad we always mean symmetric colored operad or, equivalently, symmetric multicategory.

2.2. Monoidal categories and operads. In Section 3, we will construct the symmetric monoidal category (W, ⊕, 0) of boxes and wiring diagrams, which we often simply denote as W. We will sometimes consider the underlying operad OW, obtained by applying the fully faithful functor

O: SMC → Opd

to W. A brief description of this functor O is given below in Definition 2.3.

2.3. Definition. Let SMC denote the category of symmetric monoidal categories and lax monoidal functors; and Opd be the category of operads and operad functors. Given a symmetric monoidal category (C, ⊗, I_{C}) ∈ Ob SMC, we define the operad OC as follows:

Ob OC := Ob C, Hom_{OC}(X_{1}, …, X_{n}; Y) := Hom_{C}(X_{1} ⊗ ⋯ ⊗ X_{n}, Y)

for any n ∈ ℕ and objects X_{1}, …, X_{n}, Y ∈ Ob C.

Now suppose F: (C, ⊗, I_{C}) → (D, ⊙, I_{D}) is a lax monoidal functor in SMC. By definition such a functor is equipped with a morphism

μ: F X_{1} ⊙ ⋯ ⊙ F X_{n} → F (X_{1} ⊗ ⋯ ⊗ X_{n}),

natural in the X_{i}, called the coherence map. With this map in hand, we define the operad functor OF: OC → OD by stating how it acts on objects X and morphisms Φ: X_{1}, …, X_{n} → Y in OC:

OF (X) := F (X), OF (Φ: X_{1}, …, X_{n} → Y) := F (Φ) ∘ μ: F X_{1} ⊙ ⋯ ⊙ F X_{n} → F Y.

2.4. Example. Consider the symmetric monoidal category (Set, ×, ⋆), where × is the cartesian product of sets and ⋆ a one element set. Define Sets := OSet as in Definition 2.3. Explicitly, Sets is the operad in which an object is a set and a morphism f: X_{1}, …, X_{n} → Y is a function f: X_{1} × ⋯ × X_{n} → Y.

2.5. Definition. Let C be a symmetric monoidal category and let Set = (Set, ×, ⋆) be as in Example 2.4. A C-algebra is a lax monoidal functor C → Set. Similarly, if D is an operad, a D-algebra is defined as an operad functor D → Sets.

To avoid subscripts, we will generally use the formalism of SMCs in this paper. Definitions 2.3 and 2.5 can be applied throughout to recast everything we do in terms of operads. The primary reason operads may be preferable in applications is that they suggest more compelling pictures. Hence throughout this paper, depictions of wiring diagrams will often be operadic, i.e., have many input boxes wired together into one output box.

2.6. Typed sets. Each box in a wiring diagram will consist of finite sets of ports, each labelled by a type. To capture this idea precisely, we define the notion of typed finite sets. By a finite product category, we mean a category that is closed under taking finite products.

2.7. Definition. Let C be a small finite product category. The category of C-typed finite sets, denoted TFS_{C}, is defined as follows. An object in TFS_{C} is a map from a finite set to the objects of C:

Ob TFS_{C} := {(A, τ) | A ∈ Ob FinSet, τ: A → Ob C)}.

Intuitively, one can think of a typed finite set as a finite unordered list of C-objects. For any element a ∈ A, we call the object τ(a) its type. If the typing function τ is clear from context, we may denote (A, τ) simply by A.

A morphism q: (A, τ) → (A′, τ′) in TFS_{C} consists of a function q: A → A′ that makes the following diagram of finite sets commute:

\xymatrix{A \ar[rr]^{q} \ar[dr]_{τ} &  & A′ \ar[dl]^{τ′} \\  & Ob C}

Note that TFS_{C} is a cocartesian monoidal category.

We refer to the morphisms of TFS_{C} as C-typed functions. If a C-typed function q is bijective, we call it a C-typed bijection.

In other words, TFS_{C} is the comma category for the diagram

FinSet ⟶^{i} Set ⟵^{Ob C} {∗}

where i is the inclusion.

2.8. Definition. Let C be a finite product category, and let (A, τ) ∈ Ob TFS_{C} be a C-typed finite set. Its dependent product \overline{(A, τ)} ∈ Ob C is defined as

\overline{(A, τ)} := ∏_{a∈A} τ(a).

Coordinate projections and diagonals are generalized as follows. Given a typed function q: (A, τ) → (A′, τ′) in TFS_{C} we define

\overline{q}: \overline{(A′, τ′)} → \overline{(A, τ)}

to be the unique morphism for which the following diagram commutes for all a ∈ A:

[figure: ∏_{a′∈A′} τ′(a′); \overline{q}; π_{q(a)}; ∏_{a∈A} τ(a); π_{a}; τ′(q(a)); τ(a)]

By the universal property for products, this defines a functor,

\overline{·} : TFS_{C}^{op} → C.

2.9. Lemma. The dependent product functor TFS_{C}^{op} → C is strong monoidal. In particular, for any finite set I whose elements index typed finite sets (A_{i}, τ_{i}), there is a canonical isomorphism in C,

\overline{∐_{i∈I}(A_{i}, τ_{i})} ≅ ∏_{i∈I} \overline{(A_{i}, τ_{i})}.

2.10. Remark. The category of second-countable smooth manifolds and smooth maps is essentially small (by the embedding theorem) so we choose a small representative and denote it Man. Note that Man is a finite product category. Manifolds will be our default typing, in the sense that we generally take C := Man in Definition 2.7 and denote

TFS := TFS_{Man}.  (2)

We thus refer to the objects, morphisms, and isomorphisms in TFS simply as typed finite sets, typed functions, and typed bijections, respectively.

2.11. Remark. The ports of each box in a wiring diagram will be labeled by manifolds because they are the natural setting for geometrically interpreting differential equations (see [Spi65]). For simplicity, one may wish to restrict attention to the full subcategory Euc of Euclidean spaces ℝ^{n} for n ∈ ℕ, because they are the usual domains for ODEs found in the literature; or to the (non-full) subcategory Lin of Euclidean spaces and linear maps between them, because they characterize linear systems of ODEs. We will return to TFS_{Lin} in Section 5.

2.12. Open systems. As a final preliminary, we define our notion of open dynamical system. Recall that every manifold M has a tangent bundle manifold, denoted T M, and a smooth projection map p: T M → M. For any point m ∈ M, the preimage T_{m}M := p^{−1}(m) has the structure of a vector space, called the tangent space of M at m. If M ≅ ℝ^{n} is a Euclidean space then also T_{m}M ≅ ℝ^{n} for every point m ∈ M. A vector field on M is a smooth map g: M → T M such that p ∘ g = id_{M}. See [Spi65] or [War83] for more background.

For the purposes of this paper we make the following definition of open systems; this may not be completely standard.

2.13. Definition. Let M, U^{in}, U^{out} ∈ Ob Man be smooth manifolds and T M be the tangent bundle of M. Let f = (f^{in}, f^{out}) denote a pair of smooth maps

\begin{cases}f^{in} : M × U^{in} → T M \\ f^{out} : M → U^{out} \end{cases}

where, for all (m, u) ∈ M × U^{in} we have f^{in}(m, u) ∈ T_{m}M; that is, the following diagram commutes:

\xymatrix{M × U^{in} \ar[rr]^{f^{in}} \ar[dr]_{π_{M}} &  & T M \ar[dl]^{p} \\  & M}

We sometimes use f to denote the whole tuple,

f = (M, U^{in}, U^{out}, f),

which we refer to as an open dynamical system (or open system for short). We call M the state space, U^{in} the input space, U^{out} the output space, f^{in} the differential equation, and f^{out} the readout map of the open system.

Note that the pair f = (f^{in}, f^{out}) is determined by a single smooth map

f: M × U^{in} → T M × U^{out},

which, by a minor abuse of notation, we also denote by f.

In the special case that M, U^{in}, U^{out} ∈ Ob Lin are Euclidean spaces and f is a linear map (or equivalently f^{in} and f^{out} are linear), we call f a linear open system.

2.14. Remark. Let M be a smooth manifold, and let U^{in} = U^{out} = ℝ^{0} be trivial. Then an open system in the sense of Definition 2.13 is a smooth map f: M → T M over M, in other words, a vector field on M. From the geometric point of view, vector fields are autonomous (i.e., closed!) dynamical systems; see [Tes12].

2.15. Remark. For an arbitrary manifold U^{in}, a map M × U^{in} → T M can be considered as a function U^{in} → VF(M), where VF(M) is the set of vector fields on M. Hence, U^{in} controls the behavior of the system in the usual sense.

2.16. Remark. Given an open system f we can form a new open system by feeding the readout of f into the inputs of f. For example suppose the open system is of the form

\begin{cases}M × A × B ⟶^{F} T M \\ g = (g_{A}, g_{B}): M → C × B, \end{cases}

where A, B, C and M are manifolds. Define F′: M × A → T M by

F′(m, a) := F (m, a, g_{B}(m)) for all (m, a) ∈ M × A.

Then

\begin{cases}M × A ⟶^{F′} T M \\ g_{A}: M → C \end{cases}

is a new open system obtained by plugging a readout of f into the space of inputs B. Compare with Figure 3.

This looks a little boring. It becomes more interesting when we start with several open systems, take their product and then plug (some of the) outputs into inputs. For example suppose we start with two open systems

\begin{cases}M_{1} × A × B ⟶^{F_{1}} T M_{1} \\ g_{1} : M_{1} → C \end{cases}

and

\begin{cases}M_{2} × C ⟶^{F_{2}} T M_{2} \\ g_{2} = (g_{B}, g_{D}): M_{2} → B × D \end{cases} .

Here, again, all capital letters denote manifolds. Take their product; we get

\begin{cases}M_{1} × A × B × M_{2} × C ⟶^{(F_{1},F_{2})} T M_{1} × T M_{2} \\ (g_{1}, g_{2}): M_{1} × M_{2} → C × B × D \end{cases}

Now plug in the functions g_{B} and g_{1} into inputs. We get a new system

\begin{cases}M_{1} × M_{2} × A ⟶^{F′} T M_{1} × T M_{2} \\ g′: M_{1} × M_{2} → D \end{cases}

where

F′(m_{1}, m_{2}, a) := (F_{1}(m_{1}, a, g_{B}(m_{2})), F_{2}(m_{2}, g_{1}(m_{1})).

Compare with Figure 7.

Making these kinds of operations on open systems precise for an arbitrary number of interacting systems is the point of our paper.

By defining the appropriate morphisms, we can consider open dynamical systems as being objects in a category. We are not aware of this notion being defined previously in the literature, but it is convenient for our purposes.

2.17. Definition. Suppose that M_{i}, U_{i}^{in}, U_{i}^{out} ∈ Ob Man and (M_{i}, U_{i}^{in}, U_{i}^{out}, f_{i}) is an open system for i ∈ {1, 2}. A morphism of open systems

ζ: (M_{1}, U_{1}^{in}, U_{1}^{out}, f_{1}) → (M_{2}, U_{2}^{in}, U_{2}^{out}, f_{2})

is a triple (ζ_{M}, ζ_{U^{in}}, ζ_{U^{out}}) of smooth maps ζ_{X}: X_{1} → X_{2} for X ∈ {M, U^{in}, U^{out}} such that the following diagram commutes:

\xymatrix{M_{1} × U_{1}^{in} \ar[r]^{f_{1}} \ar[d]_{ζ_{M} ×ζ_{U^{in}}} & T M_{1} × U_{1}^{out} \ar[d]^{T ζ_{M} ×ζ_{U^{out}}} \\ M_{2} × U_{2}^{in} \ar[r]_{f_{2}} & T M_{2} × U_{2}^{out}}

This defines the category ODS of open dynamical systems. We define the subcategory ODS_{Lin} ⊆ ODS by restricting our objects to linear open systems, as in Definition 2.13, and imposing that the three maps in ζ are linear.

As in Remark 2.16, we will often want to combine two or more interconnected open systems into one larger one. As we shall see in Section 4, this will involve taking a product of the smaller open systems. Before we define this formally, we first remind the reader that the tangent space functor T is strong monoidal, i.e., it canonically preserves products,

T (M_{1} × M_{2}) ≅ T M_{1} × T M_{2}.

2.18. Lemma. The category ODS of open systems has all finite products. That is, if I is a finite set and f_{i} = (M_{i}, U_{i}^{in}, U_{i}^{out}, f_{i}) ∈ Ob ODS is an open system for each i ∈ I, then their product is

∏_{i∈I} f_{i} = (∏_{i∈I} M_{i}, ∏_{i∈I} U_{i}^{in}, ∏_{i∈I} U_{i}^{out}, ∏_{i∈I} f_{i})

with the obvious projection maps.

3. The Operad of Wiring Diagrams

In this section, we define the symmetric monoidal category (W, ⊕, 0) of wiring diagrams. We then use Definition 2.3 to define the wiring diagram operad OW, which situates our pictorial setting. We begin by formally defining the underlying category W and continue with some concrete examples to explicate this definition.

3.1. Definition. The category W has objects boxes and morphisms wiring diagrams. A box X is an ordered pair of Man-typed finite sets (Definition 2.7),

X = (X^{in}, X^{out}) ∈ Ob TFS × Ob TFS.

Let X^{in} = (A, τ) and X^{out} = (A′, τ′). Then we refer to elements a ∈ A and a′ ∈ A′ as input ports and output ports, respectively. We call τ(a) ∈ Ob Man the type of port a, and similarly for τ′(a′).

A wiring diagram Φ: X → Y in W is a triple (X, Y, φ), where φ is a typed bijection (see Definition 2.7)

φ: X^{in} + Y^{out} ⟶^{≅} X^{out} + Y^{in},  (3)

satisfying the following condition:

no passing wires φ(Y^{out}) ∩ Y^{in} = ∅, or equivalently φ(Y^{out}) ⊆ X^{out}.

This condition allows us to decompose φ into a pair φ = (φ^{in}, φ^{out}):

\{ \begin{matrix}φ^{in} : X^{in} → X^{out} + Y^{in} \\ φ^{out} : Y^{out} → X^{out} \end{matrix}  (4)

We often identify the wiring diagram Φ = (X, Y, φ) with the typed bijection φ, or equivalently its corresponding pair (φ^{in}, φ^{out}).

By a wire in Φ, we mean a pair (a, b), where a ∈ X^{in} + Y^{out}, b ∈ X^{out} + Y^{in}, and φ(a) = b. In other words a wire in Φ is a pair of ports connected by ϕ.

The identity wiring diagram ι: X → X is given by the identity morphism X^{in}+X^{out} → X^{in} + X^{out} in TFS.

Now suppose Φ = (X, Y, φ) and Ψ = (Y, Z, ψ) are wiring diagrams. We define their composition as Ψ ∘ Φ = (X, Z, ω), where ω = (ω^{in}, ω^{out}) is given by the pair of dashed arrows making the following diagrams commute.

\xymatrix{X^{in} \ar[dd]_{φ^{in}} \ar@{-->}[r]^{ω^{in}} & X^{out} + Z^{in} & Z^{out} \ar[dr]_{ψ^{out}} \ar@{-->}[rr]^{ω^{out}} &  & X^{out} \\  & X^{out} + X^{out} + Z^{in} \ar[u]_{∇+𝟙_{Z^{in}}} &  & Y^{out} \ar[ur]_{φ^{out}} \\ X^{out} + Y^{in} \ar[r]_{𝟙_{X^{out}}+ψ^{in}} & X^{out} + Y^{out} + Z^{in} \ar[u]_{𝟙_{X^{out}}+φ^{out}+𝟙_{Z^{in}}}}  (5)

Here ∇: X^{out} + X^{out} → X^{out} is the codiagonal map in TFS.

3.2. Remark. For any finite product category C, we may define the category W_{C} by replacing Man with C, and TFS with TFS_{C}, in Definition 3.1. In particular, as in Remark 2.11, we have the symmetric monoidal category W_{Lin} of linearly typed wiring diagrams.

What we are calling a box is nothing more than an interface; at this stage it has no semantics, e.g., in terms of differential equations. Each box can be given a pictorial representation, as in Example 3.3 below.

3.3. Example. As a convention, we depict a box X = ({a, b}, {c}) with input ports connecting on the left and output ports connecting on the right, as in Figure 2 below. When types are displayed, we label ports on the exterior of their box and their types adjacently on the interior of the box with a ‘:’ symbol in between to designate typing. Reading types off of this figure, we see that the type of input port a is the manifold ℝ, that of input port b is the circle S^{1}, and that of output port c is the torus T^{2}.

X a : ℝ b : S^{1} : c T^{2}

Figure 2: A box with two input ports, of types ℝ and S^{1}, and one output port with type T^{2}.

A morphism in W is a wiring diagram Φ = (X, Y, φ), the idea being that a smaller box X (the domain) is nested inside of a larger box Y (the codomain). The ports of X and Y are then interconnected by wires, as specified by the typed bijection φ. We will now see an example of a wiring diagram, accompanied by a picture.

3.4. Example. Reading off the wiring diagram Φ = (X, Y, φ) drawn below in Figure 3, we have the following data for boxes:

X^{in} = {a, b} X^{out} = {c, d}
Y^{in} = {m} Y^{out} = {n}

Table 1 makes φ explicit via a list of its wires, i.e., pairs (γ, φ(γ)).

γ ∈ X^{in} + Y^{out} a b n ; φ(γ) ∈ X^{out} + Y^{in} m d c

Table 1

\begin{matrix}Y \\ m \\ n \\ X \\ a \\ b \\ c \\ d \end{matrix}

Figure 3: A Wiring Diagram Φ = (X, Y, φ).

3.5. Remark. The condition that φ be typed, as in Definition 2.7, ensures that if two ports are connected by a wire then the associated types are the same. In particular, in Example 3.4 above, (a, b, n) must be the same type tuple as (m, d, c).

Now that we have made wiring diagrams concrete and visual, we can do the same for their composition.

3.6. Example. In Figure 4, we visualize the composition of two wiring diagrams Φ = (X, Y, φ) and Ψ = (Y, Z, ψ) to form Ψ ∘ Φ = (X, Z, ω). Composition is depicted by drawing the wiring diagram for Ψ and then, inside of the Y box, drawing in the wiring diagram for Φ. Finally, to depict the composition Ψ ∘ Φ as one single wiring diagram, one simply “erases” the Y box, leaving the X and Z boxes interconnected among themselves. Figure 4 represents such a procedure by depicting the Y box with a dashed arrow.

It’s important to note that the wires also connect, e.g. if a wire in Ψ connects a Z port to some Y port, and that Y port attaches via a Φ wire to some X port, then these wires “link together” to a total wire in Ψ ∘ Φ, connecting a Z port with an X port. Table 2 below traces the wires of Ψ ∘ Φ through the ω^{in} and ω^{out} composition diagrams in (5) on its left and right side, respectively. The left portion of the table starts with γ ∈ X^{in} and ends at ω^{in}(γ) ∈ X^{out} + Z^{in}, with intermediary steps of the composition denoted with superscripts γ^{n}. The right portion of the table starts with γ ∈ Z^{out} then goes through the intermediary of γ′ ∈ Y^{out} and finally reaches ω^{out}(γ) ∈ Z^{out}. We skip lines on the right portion to match the spacing on the left.

γ ∈ X^{in} a b c v γ ∈ Z^{out}
γ^{1} ∈ X^{out} + Y^{in}  d k l
γ^{2} ∈ X^{out} + Y^{out} + Z^{in} d u n m  γ′ ∈ Y^{out}
γ^{3} ∈ X^{out} + X^{out} + Z^{in} d u f
ω^{in}(γ) ∈ X^{out} + Z^{in} d u f e ω^{out}(γ) ∈ X^{out}

Table 2

\begin{matrix}Z \\ u \\ v \\ Y \\ k \\ m \\ l \\ n \\ X \\ c \\ b \\ a \\ f \\ e \\ d \end{matrix}

Figure 4: A wiring diagram composition Ψ ∘ Φ = (X, Z, ω) of Φ = (X, Y, φ) and Ψ = (Y, Z, ψ), with dashed medium box Y.

3.7. Remark. The condition that φ be both injective and surjective prohibits exposed ports and split ports, respectively, as depicted in Figure 5a. The no passing wires condition on φ(Y^{out}) prohibits wires that go straight across the Y box, as seen in the intermediate box of Figure 5b.

Now that we have formally defined and concretely explicated the category W, we will make it into a monoidal category by defining its tensor product.

3.8. Definition. Let X_{1}, X_{2}, , Y_{1}, Y_{2} ∈ Ob W be boxes and Φ_{1} : X_{1} → Y_{2} and Φ_{2} : X_{2} → Y_{2} be wiring diagrams. The monoidal product ⊕ is given by

X_{1} ⊕ X_{2} := (X_{1}^{in} + X_{2}^{in} , X_{1}^{out} + X_{2}^{out} ) , Φ_{1} ⊕ Φ_{2} := Φ_{1} + Φ_{2}.

The closed box 0 = {∅, ∅} is the monoidal unit.

\begin{matrix}a \\ Y \\ X \\ b \\ Z \\ Y \\ X \end{matrix}

Figure 5: (a) A faux-wiring diagram failing the bijectivity condition in Definition 3.1.

(b) A composition of diagrams in which a loop emerges because the inner diagram has a (prohibited) passing wire.

3.9. Remark. Once we add semantics in Section 4, closed boxes will correspond to autonomous systems, which do not interact with any outside environment (see Remark 2.14).

We now make this monoidal product explicit with an example.

3.10. Example. Consider boxes X = ({x_{1}, x_{2}}, {x_{3}, x_{4}}) and Y = ({y_{1}}, {y_{2}, y_{3}}) depicted below.

\begin{matrix}X \\ x_{1} \\ x_{2} \\ x_{3} \\ x_{4} \\ Y \\ y_{1} \\ y_{2} \\ y_{3} \end{matrix}

We depict their tensor X ⊕ Y = ({x_{1}, x_{2}, y_{1}}, {x_{3}, x_{4}, y_{2}, y_{3}}) by stacking boxes.

\begin{matrix}X ⊕ Y \\ x_{1} \\ x_{2} \\ y_{1} \\ x_{3} \\ x_{4} \\ y_{2} \\ y_{3} \end{matrix}

Similarly, consider the following wiring diagrams (with ports left unlabelled).

\begin{matrix}Φ_{1} : X_{1} → Y_{1} \\ Y_{1} \\ X_{1} \\ Φ_{2} : X_{2} → Y_{2} \\ Y_{2} \\ X_{2} \end{matrix}

We can depict their composition via stacking.

Φ_{1} ⊕ Φ_{2} : X_{1} ⊕ X_{2} → Y_{1} ⊕ Y_{2} Y_{1} ⊕ Y_{2} X_{1} ⊕ X_{2}

We now prove that the above data characterizing (W, ⊕, 0) indeed constitutes a symmetric monoidal category, at which point we can, as advertised, invoke Definition 2.3 to define the operad OW.

3.11. Proposition. The category W in Definition 3.1 and the monoidal product ⊕ with unit 0 in Definition 3.8 form a symmetric monoidal category (W, ⊕, 0).

Proof. We begin by establishing that W is indeed a category. We first show that our class of wiring diagrams is closed under composition. Let Φ = (X, Y, φ), Ψ = (Y, Z, ψ), and Ψ ∘ Φ = (X, Z, ω).

To show that ω is a typed bijection, we replace the pair of maps (φ^{in}, φ^{out}) with a pair of bijections (φ̃^{in}, φ̃^{out}) as follows. Let X_{φ}^{exp} ⊆ X^{out} (for exports) denote the image of φ^{out}, and X_{φ}^{loc} (for local ports) be its complement. Then we can identify φ with the following pair of typed bijections

\{ \begin{matrix}φ̃^{in} : X^{in} ⟶^{≅} X_{φ}^{loc} + Y^{in} \\ φ̃^{out} : Y^{out} ⟶^{≅} X_{φ}^{exp} \end{matrix}

Similarly, identify ψ with (ψ̃^{in}, ψ̃^{out}). We can then rewrite the diagram defining ω in (5) as one single commutative diagram of typed finite sets.

\xymatrix{X^{in} + Z^{out} \ar[d]_{φ̃^{in}+ψ̃^{out}} \ar@{-->}[r]^{ω} & X^{out} + Z^{in} \\ X_{φ}^{loc} + Y^{in} + Y_{ψ}^{exp} \ar[d]_{𝟙_{X{loc \atop φ}}+ψ̃^{in}+𝟙_{Y{exp \atop ψ}}} & X_{φ}^{loc} + X_{φ}^{exp} + Z^{in} \ar[u]_{≅} \\ X_{φ}^{loc} + Y_{ψ}^{loc} + Z^{in} + Y_{ψ}^{exp} \ar[r]_{≅} & X_{φ}^{loc} + Y^{out} + Z^{in} \ar[u]_{𝟙_{X{loc \atop φ}}+φ̃^{out}+𝟙_{Z^{in}}}}

As a composition of typed bijections, ω is also a typed bijection.

The following computation proves that ω has no passing wires:

ω(Z^{out}) = φ(ψ(Z^{out})) ⊆ φ(Y^{out}) ⊆ X^{out}.

Therefore W is closed under wiring diagram composition. To show that W is a category, it remains to prove that composition of wiring diagrams satisfies the unit and associativity axioms. The former is straightforward and will be omitted. We now establish the latter.

Consider the wiring diagrams Θ = (V, X, θ), Φ = (X, Y, φ), Ψ = (Y, Z, ψ); and let (Ψ ∘ Φ) ∘ Θ = (V, Z, κ) and Ψ ∘ (Φ ∘ Θ) = (V, Z, λ). We readily see that κ^{out} = λ^{out} by the associativity of composition in TFS. Proving that κ^{in} = λ^{in} is equivalent to establishing the commutativity of the following diagram:

\xymatrix{ & V^{out} + Z^{in} \\  & V^{out} + V^{out} + Z^{in} \ar[u]^{∇+𝟙} \\ V^{out} + Y^{out} + Z^{in} \ar[r]^{𝟙+φ^{out}+𝟙} & V^{out} + X^{out} + Z^{in} \ar[u]^{𝟙+θ^{out}+𝟙} & V^{out} + X^{out} + X^{out} + Z^{in} \ar[l]_{𝟙+∇+𝟙} \\ V^{out} + Y^{in} \ar[u]^{𝟙+ψ^{in}} \\ V^{out} + V^{out} + Y^{in} \ar[u]^{∇+𝟙} & V^{out} + X^{out} + Y^{in} \ar[l]^{𝟙+θ^{out}+𝟙} \ar[r]_{𝟙+𝟙+ψ^{in}} & V^{out} + X^{out} + Y^{out} + Z^{in} \ar[uu]_{𝟙+𝟙+φ^{out}+𝟙} \\  & V^{out} + X^{in} \ar[u]^{𝟙+φ^{in}} \\  & V^{in} \ar[u]^{θ^{in}}} (6)

This diagram commutes in any category with coproducts, as follows from the associativity and naturality of the codiagonal map. We present a formal argument of this fact below in the language of string diagrams (See [JS91]). As in [Sel11], we let squares with blackened corners denote generic morphisms. We let triangles denote codiagonal maps. See Figure 6 below.

The first step of the proof follows from the topological nature of string diagrams, which mirror the axioms of monoidal categories. The second step invokes the associativity of codiagonal maps. The third and final step follows from the naturality of codiagonal maps, i.e., the commutativity of the following diagram.

\xymatrix{V^{out} + V^{out} \ar[r]^{∇} \ar[d]_{θ^{out}+θ^{out}} & V^{out} \ar[d]^{θ^{out}} \\ X^{out} + X^{out} \ar[r]^{∇} & X^{out}}

Now that we have shown that W is a category, we show that (⊕, 0) is a monoidal structure on W. Let X, X′, X′′ ∈ Ob W be boxes. We readily observe the following

θ^{out} ; ψ^{in} ; φ^{out} ; θ^{out} ; X^{out} ; V^{out} ; V^{out} ; Y^{out} ; Z^{in} ; X^{out} ; Y^{in} ; V^{out} ; V^{out} ; V^{out}

θ^{out} ; ψ^{in} ; φ^{out} ; θ^{out} ; V^{out} ; Y^{out} ; Z^{in} ; X^{out} ; Y^{in} ; X^{out} ; V^{out} ; V^{out} ; V^{out} ; V^{out}

θ^{out} ; ψ^{in} ; φ^{out} ; θ^{out} ; V^{out} ; Y^{out} ; Z^{in} ; X^{out} ; Y^{in} ; X^{out} ; V^{out} ; V^{out} ; V^{out} ; V^{out}

θ^{out} ; ψ^{in} ; φ^{out} ; Y^{out} ; Z^{in} ; X^{out} ; Y^{in} ; X^{out} ; X^{out} ; V^{out} ; V^{out} ; V^{out}

Figure 6: String diagram proof of commutativity of (6)

canonical isomorphisms.

X ⊕ 0 = X = 0 ⊕ X  (unity)
(X ⊕ X′) ⊕ X′′ = X ⊕ (X′ ⊕ X′′)  (associativity)
X ⊕ X′ = X′ ⊕ X  (commutativity)

Hence the monoidal product ⊕ is well behaved on objects. It is similarly easy, and hence will be omitted, to show that ⊕ is functorial. This completes the proof that (W, ⊕, 0) is a symmetric monoidal category.

Having established that (W, ⊕, 0) is an SMC, we can now speak about the operad OW of wiring diagrams. In particular, we can draw operadic pictures, such as the one in our motivating example in Figure 1, to which we now return.

3.12. Example. Figure 7 depicts an OW wiring diagram Φ: X_{1}, X_{2} → Y, which we may formally denote by the tuple Φ = (X_{1}, X_{2}; Y; φ). Reading directly from Figure 7, we have the boxes:

X_{1} = ({X_{1a}^{in}, X_{1b}^{in}}, {X_{1a}^{out}})
X_{2} = ({X_{2a}^{in}, X_{2b}^{in}}, {X_{2a}^{out}, X_{2b}^{out}})
Y = ({Y_{a}^{in}, Y_{b}^{in}}, {Y_{a}^{out}})

The wiring diagram Φ is visualized by nesting the domain boxes X_{1}, X_{2} within the codomain box Y, and drawing the wires prescribed by φ, as recorded below in Table 3.

w ∈ X^{in} + Y^{out} X_{1a}^{in} X_{1b}^{in} X_{2a}^{in} X_{2b}^{in} Y_{a}^{out} ; φ(w) ∈ X^{out} + Y^{in} Y_{b}^{in} X_{2b}^{out} Y_{a}^{in} X_{1a}^{out} X_{2a}^{out}

Table 3

Y Y_{a}^{in} Y_{b}^{in} Y_{a}^{out} X_{1} X_{1a}^{in} X_{1b}^{in} X_{1a}^{out} X_{2} X_{2a}^{in} X_{2b}^{in} X_{2a}^{out} X_{2b}^{out}
Figure 7: A wiring diagram Φ: X_{1}, X_{2} → Y in OW.

To reconceptualize Φ: X_{1}, X_{2} → Y as a wiring diagram in W, we simply consider the tensor Φ: X_{1} ⊕ X_{2} → Y, as given in Figure 8 below. This demonstrates the fact that operadic pictures are easier to read and hence are more illuminating.

The following remark explains that our pictures of wiring diagrams are not completely ad hoc—they are depictions of 1-dimensional oriented manifolds with boundary. The boxes in our diagrams simply tie together the positively and negatively oriented components of an individual oriented 0-manifold.

3.13. Remark. For any set S, let 1–Cob /S denote the symmetric monoidal category of oriented 0-manifolds over S and the 1-dimensional cobordisms between them. We call its objects oriented S-typed 0-manifolds. Recall that W = W_{Man} is our category of Mantyped wiring diagrams; let M := Ob Man denote the set of manifolds (see Remark 2.10). There is a faithful, essentially surjective, strong monoidal functor

W → 1–Cob /M,

sending a box (X^{in}, X^{out}) to the oriented M-typed 0-manifold X^{in} + X^{out} where X^{in} is oriented positively and X^{out} negatively. Under this functor, a wiring diagram Φ =

Y Y_{a}^{in} Y_{b}^{in} Y_{a}^{out} X_{1} ⊕ X_{2} X_{1a}^{in} X_{1b}^{in} X_{2a}^{in} X_{2b}^{in} X_{1a}^{out} X_{2a}^{out} X_{2b}^{out}

Figure 8: A wiring diagram Φ: X_{1} ⊕ X_{2} → Y in W corresponding to the OW wiring diagram Φ: X_{1}, X_{2} → Y of Figure 7.

(X, Y, φ) is sent to a 1-dimensional cobordism that has no closed loops. A connected component of such a cobordism can be identified with either its left or right endpoint, which correspond to the domain or codomain of the bijection φ: X^{in} +Y^{out} ⟶^{≅} X^{out} +Y^{in}. See [SSR15].

In fact, with the no passing wires condition on morphisms (cobordisms) X → Y (see Definition 3.1), the subcategory W ⊆ 1–Cob /M is the left class of an orthogonal factorization system. See [Aba15].

Let Φ = (X, Y, φ) be a wiring diagram. Applying the dependent product functor (see Definition 2.8) to φ, we obtain a diffeomorphism of manifolds

\overline{φ}: \overline{X^{out}} × \overline{Y^{in}} → \overline{X^{in}} × \overline{Y^{out}}.  (7)

Equivalently, if φ is represented by the pair (φ^{in}, φ^{out}), as in Definition 3.1, we can express \overline{φ} in terms of its pair of component maps:

\{ \begin{matrix}\overline{φ^{in}} : \overline{X^{out}} × \overline{Y^{in}} → \overline{X^{in}} \\ \overline{φ^{out}} : \overline{X^{out}} → \overline{Y^{out}} \end{matrix}

It will also be useful to apply the dependent product functor to the commutative diagrams in (5), which define wiring diagram composition. Note that, by the contravariance of the dependent product, the codiagonal ∇: X^{out}+X^{out} → X^{out} gets sent to the diagonal map Δ: \overline{X^{out}} → \overline{X^{out}} × \overline{X^{out}}. Thus we have the following commutative diagrams:

\xymatrix{\overline{X^{out}} × \overline{Z^{in}} \ar[r]^{\overline{ω^{in}}} \ar[d]_{Δ×𝟙} & \overline{X^{in}} & \overline{X^{out}} \ar[dr]_{\overline{φ^{out}}} \ar[rr]^{\overline{ω^{out}}} &  & \overline{Z^{out}} \\ \overline{X^{out}} × \overline{X^{out}} × \overline{Z^{in}} \ar[d]_{𝟙×\overline{φ^{out}}×𝟙} &  &  & \overline{Y^{out}} \ar@{-->}[ur]_{\overline{ψ^{out}}} \\ \overline{X^{out}} × \overline{Y^{out}} × \overline{Z^{in}} \ar[r]_{𝟙×\overline{ψ^{in}}} & \overline{X^{out}} × \overline{Y^{in}} \ar[uu]_{\overline{φ^{in}}}}  (8)

4. The Algebra of Open Systems

In this section we define an algebra G: (W, ⊕, 0) → (Set, ×, ⋆) (see Definition 2.5) of general open dynamical systems. A W-algebra can be thought of as a choice of semantics for the syntax of W, i.e., a set of possible meanings for boxes and wiring diagrams. As in Definition 2.3, we may use this to construct the corresponding operad algebra OG: OW → Sets. Before we define G, we revisit Example 1.2 for inspiration.

4.1. Example. As the textbook exercise [BD65, Problem 7.21] prompts, let’s begin by writing down the system of equations that governs the amount of salt Q_{i} within the tanks X_{i}. This can be done by using dimensional analysis for each port of X_{i} to find the rate of salt being carried in ounces per minute, and then equating the rate Q̇_{i} to the sum across these rates for X_{i}^{in} ports minus X_{i}^{out} ports.

Q̇_{1} \frac{oz}{min} = − (\frac{Q_{1}oz}{30gal} · \frac{3gal}{min}) + (\frac{Q_{2}oz}{20gal} · \frac{1.5gal}{min}) + (\frac{1oz}{gal} · \frac{1.5gal}{min})
Q̇_{2} \frac{oz}{min} = − (\frac{Q_{2}oz}{20gal} · \frac{(1.5 + 2.5)gal}{min}) + (\frac{Q_{1}oz}{30gal} · \frac{3gal}{min}) + (\frac{3oz}{gal} · \frac{1gal}{min})

Dropping the physical units, we are left with the following system of ODEs:

\{ \begin{matrix}Q̇_{1} = −.1Q_{1} + .075Q_{2} + 1.5 \\ Q̇_{2} = .1Q_{1} − .2Q_{2} + 3 \end{matrix}  (9)

The derivations for the equations in (9) involved a hidden step in which the connection pattern in Figure 1, or equivalently Figure 7, was used. Our wiring diagram approach explains this step and makes it explicit. Each box in a wiring diagram should only “know” about its own inputs and outputs, and not how they are connected to others. That is, we can only define a system on X_{i} by expressing Q̇_{i} just in terms of Q_{i} and X_{i}^{in}—this is precisely the data of an open system (see Definition 2.13). We now define our algebra G, which assigns a set of open systems to a box. Given a wiring diagram and an open system on its domain box, it also gives a functorial procedure for assigning an open system to the codomain box. We will then use this new machinery to further revisit Example 4.1 in Example 5.7.

4.2. Definition. We define G: (W, ⊕, 0) → (Set, ×, ⋆) as follows. Let X ∈ Ob W. The set of open systems on X, denoted G(X), is defined as

G(X) = \{(S, f) | S ∈ Ob TFS, (\overline{S}, \overline{X^{in}}, \overline{X^{out}}, f) ∈ Ob ODS\}.

We call S the set of state variables and its dependent product \overline{S} the state space.

Let Φ = (X, Y, φ) be a wiring diagram. Then G(Φ): G(X) → G(Y) is given by (S, f) ↦ (G(Φ)S, G(Φ)f), where G(Φ)S = S and g = G(Φ)f: \overline{S} × \overline{Y^{in}} → T \overline{S} × \overline{Y^{out}} is defined by the dashed arrows (g^{in}, g^{out}) (see Definition 2.13) that make the diagrams below commute:

\xymatrix{\overline{S} × \overline{Y^{in}} \ar[d]_{Δ×𝟙\overline{Y^{in}}} \ar@{-->}[r]^{g^{in}} & T \overline{S} & \overline{S} \ar[dr]_{f^{out}} \ar@{-->}[rr]^{g^{out}} &  & \overline{Y^{out}} \\ \overline{S} × \overline{S} × \overline{Y^{in}} \ar[d]_{𝟙\overline{S}×f^{out}×𝟙\overline{Y^{in}}} &  &  & \overline{X^{out}} \ar@{-->}[ur]_{\overline{φ^{out}}} \\ \overline{S} × \overline{X^{out}} × \overline{Y^{in}} \ar[r]_{𝟙\overline{S}×\overline{φ^{in}}} & \overline{S} × \overline{X^{in}} \ar[uu]_{f^{in}}}  (10)

One may note strong resemblance between the diagrams in (10) and those in (5).

We give G a lax monoidal structure: for any pair X, X′ ∈ W we have a coherence map μ_{X,X′}: G(X) × G(X′) → G(X ⊕ X′) given by

((S, f), (S′, f′)) ↦ (S + S′, f × f′),

where f × f′ is as in Lemma 2.18.

4.3. Remark. Recall from Remark 2.10 that Man is small, so the collection G(X) of open systems on X is indeed a set.

4.4. Remark. One may also encode an initial condition in G by using Man_{∗} instead of Man in Remark 2.10 as the default choice of finite product category, where Man_{∗} is the category of pointed smooth manifolds and base point preserving smooth maps. The base point represents the initialization of the state variables.

We now establish that G is indeed an algebra.

4.5. Proposition. The pair (G, μ) of Definition 4.2 is a lax monoidal functor, i.e., G is a W-algebra.

Proof. Let Φ = (X, Y, φ) and Ψ = (Y, Z, ψ) be wiring diagrams in W. To show that G is a functor, we must have that G(Ψ ∘ Φ) = G(Ψ) ∘ G(Φ). Immediately we have G(Ψ ∘ Φ)S = S = G(Ψ)(G(Φ)S).

Now let h := G(Ψ ∘ Φ)f and k := G(Ψ)(G(Φ)f). It suffices to show h = k, or equivalently (h^{in}, h^{out}) = (k^{in}, k^{out}). One readily sees that h^{out} = k^{out}. We use (8) and (10) to produce the following diagram; showing it commutes is equivalent to proving that h^{in} = k^{in}.

\xymatrix{ & \overline{S} × \overline{Z^{in}} \ar[d]^{Δ×𝟙} \\  & \overline{S} × \overline{S} × \overline{Z^{in}} \ar[d]^{𝟙×f^{out}×𝟙} \\ \overline{S} × \overline{Y^{out}} × \overline{Z^{in}} \ar[d]_{𝟙×\overline{ψ^{in}}} & \overline{S} × \overline{X^{out}} × \overline{Z^{in}} \ar[l]_{𝟙×\overline{φ^{out}}×𝟙} \ar[r]^{𝟙×Δ×𝟙} & \overline{S} × \overline{X^{out}} × \overline{X^{out}} × \overline{Z^{in}} \ar[dd]^{𝟙×𝟙×\overline{φ^{out}}×𝟙} \\ \overline{S} × \overline{Y^{in}} \ar[d]_{Δ×𝟙} \\ \overline{S} × \overline{S} × \overline{Y^{in}} \ar[r]_{𝟙×f^{out}×𝟙} & \overline{S} × \overline{X^{out}} × \overline{Y^{in}} \ar[d]^{𝟙×\overline{φ^{in}}} & \overline{S} × \overline{X^{out}} × \overline{Y^{out}} × \overline{Z^{in}} \ar[l]^{𝟙×𝟙×\overline{ψ^{in}}} \\  & \overline{S} × \overline{X^{in}} \ar[d]^{f^{in}} \\  & T \overline{S}}  (11)

The commutativity of this diagram, which is dual to the one for associativity in (6), holds in an arbitrary category with products. Although the middle square fails to commute by itself, the composite of the first two maps equalizes it; that is, the two composite morphisms \overline{S} × \overline{Z^{in}} → \overline{S} × \overline{X^{out}} × \overline{Y^{in}} agree.

Since we proved the analogous result via string diagrams in the proof of Proposition 3.11, we show it concretely using elements this time. Let (s, z) ∈ \overline{S} × \overline{Z^{in}} be an arbitrary element. Composing six morphisms \overline{S} × \overline{Z^{in}} ⟶ \overline{S} × \overline{X^{out}} × \overline{Y^{in}} through the left of the diagram gives the same answer as composing through the right; namely,

(s, f^{out}(s), ψ^{in}(φ^{out} ∘ f^{out}(s), z)) ∈ \overline{S} × \overline{X^{out}} × \overline{Y^{in}}.

Since the diagram commutes, we have shown that G is a functor. To prove that the pair (G, μ) constitutes a lax monoidal functor W → Set, i.e., a W-algebra, we must establish coherence. Since μ simply consists of a coproduct and a product, this is straightforward and will be omitted.

As established in Definition 2.3, the coherence map μ allows us to define the operad algebra OG from G. This finally provides the formal setting to consider open dynamical systems over operadic wiring diagrams, such as our motivating one in Figure 1. We note that, in contrast to the trivial equality G(Φ)S = S found in Definition 4.2, in the operadic setting we have

OG(Φ)(S_{1}, …, S_{n}) = ⨿_{i=1}^{n}S_{i}.

This simply means that the set of state variables of the larger box Y is the disjoint union of the state variables of its constituent boxes X_{i}. Now that we have the tools to revisit Example 4.1, we do so in the following section, but first we will define the subalgebra L to which it belongs—that of linear open systems.

5. The Subalgebra of Linear Open Systems

In this section, we define the algebra L: W_{Lin} → Set, which encodes linear open systems. Here W_{Lin} is the category of Lin-typed wiring diagrams, as in Remark 3.2. Of course, one can use Definition 2.3 to construct an operad algebra OL : OW_{Lin} → Sets.

Before we give a formal definition for L, we first provide an alternative description for linear open systems and wiring diagrams in W_{Lin}. The category Lin enjoys special properties—in particular it is an additive category, as seen by the fact that there is an equivalence of categories Lin ≅ Vect_{ℝ}. Specifically, finite products and finite coproducts are isomorphic. Hence a morphism f: A_{1} × A_{2} → B_{1} × B_{2} in Lin canonically decomposes into a matrix equation

[\begin{matrix}a_{1} \\ a_{2} \end{matrix}] ↦ [\begin{matrix}b_{1} \\ b_{2} \end{matrix}] = [\begin{matrix}f^{1,1} & f^{1,2} \\ f^{2,1} & f^{2,2} \end{matrix}] [\begin{matrix}a_{1} \\ a_{2} \end{matrix}]

This matrix is naturally equivalent to the whole map f by universal properties. We use these to rewrite our relevant Lin maps in Definitions 5.1 and 5.2 below.

5.1. Definition. Suppose that (M, U^{in}, U^{out}, f) is a linear open system. Hence we have a linear map f: M × U^{in} → T M × U^{out}, which decomposes into four linear maps:

f^{M,M}: M → T M  f^{M,U}: U^{in} → T M
f^{U,M}: M → U^{out}  f^{U,U}: U^{in} → U^{out}

By Definition 2.13, we know f^{U,U} = 0. If we let (m, u^{in}, u^{out}) ∈ M × U^{in} × U^{out}, these equations can be organized into a single matrix equation

[ ṁ ; u^{out}] = [\begin{matrix}f^{M,M} & f^{M,U} \\ f^{U,M} & 0 \end{matrix}] [\begin{matrix}m \\ u^{in} \end{matrix}]  (12)

We will exploit this form in Definition 5.4 to define how L acts on wiring diagrams in terms of one single matrix equation, in place of the seemingly complicated commutative diagrams in (10). To do so, we also recast wiring diagrams in matrix format in Definition 5.2 below.

5.2. Definition. Suppose Φ = (X, Y, φ) is a wiring diagram in W_{Lin}. Recalling (7), we apply the dependent product functor to φ:

\overline{φ}: \overline{X^{out}} × \overline{Y^{in}} → \overline{X^{in}} × \overline{Y^{out}}

Since this is a morphism in Lin, it can be decomposed into four linear maps

\overline{φ}^{X,X}: \overline{X^{out}} → \overline{X^{in}}  \overline{φ}^{X,Y} : \overline{X^{out}} → \overline{Y^{out}}
\overline{φ}^{Y,X}: \overline{Y^{in}} → \overline{X^{out}}  \overline{φ}^{Y,Y} : \overline{Y^{in}} → \overline{Y^{out}}

By virtue of the no passing wires condition in Definition 3.1, we must have \overline{φ}^{Y,Y} = 0. We can then, as in (12), organize this information in one single matrix:

\overline{φ} = [ \begin{matrix}\overline{φ^{X,X}} & \overline{φ^{X,Y}} \\ \overline{φ^{Y,X}} & 0 \end{matrix} ]

5.3. Remark. The bijectivity condition in Definition 3.1 implies that \overline{φ} is a permutation matrix.

We now employ these matrix characterizations to define the algebra L of linear open systems.

5.4. Definition. We define the algebra L: (W_{Lin}, ⊕, 0) → (Set, ×, ⋆) as follows. Let X ∈ Ob W_{Lin}. Then the set of linear open systems L(X) on X is defined as

L(X) := \{(S, f) | S ∈ Ob TFS_{Lin}, (\overline{S}, \overline{X^{in}}, \overline{X^{out}}, f) ∈ Ob ODS_{Lin}\}.

Let Φ = (X, Y, φ) be a wiring diagram. Then, as in Definition 4.2, L(Φ)(S, f) := (S, g), where we use the format of Definitions 5.1 and 5.2 to define g:

\begin{aligned}g = [\begin{matrix}g^{S,S} & g^{S,X} \\ g^{X,S} & g^{X,X} \end{matrix}] & = [\begin{matrix}f^{S,X} & 0 \\ 0 & I \end{matrix}] \overline{φ} [\begin{matrix}f^{X,S} & 0 \\ 0 & I \end{matrix}] + [\begin{matrix}f^{S,S} & 0 \\ 0 & 0 \end{matrix}] \\ & = [\begin{matrix}f^{S,X} & 0 \\ 0 & I \end{matrix}] [\begin{matrix}\overline{φ}^{X,X} & \overline{φ}^{X,Y} \\ \overline{φ}^{Y,X} & \overline{φ}^{Y,Y} \end{matrix} ] [\begin{matrix}f^{X,S} & 0 \\ 0 & I \end{matrix}] + [\begin{matrix}f^{S,S} & 0 \\ 0 & 0 \end{matrix}] \\ & = [\begin{matrix}f^{S,X} \overline{φ}^{X,X}f^{X,S} + f^{S,S} & f^{S,X} \overline{φ}^{X,Y} \\ \overline{φ}^{Y,X}f^{X,S} & 0 \end{matrix} ] \end{aligned}  (13)

This is really just a linear version of the commutative diagrams in (10). For example, the equation g^{S,S} = f^{S,X} \overline{φ}^{X,X}f^{X,S} + f^{S,S} can be read off the diagram for g^{in} in (10), using the additivity of Lin.

Finally, The coherence map μ_{Lin_{X,X′}}: L(X) × L(X′) → L(X ⊕ X′) is given, as in Definition 4.2, by ((S, f), (S′, f′)) ↦ (S + S′, f × f′).

We now establish that this constitutes an algebra.

5.5. Proposition. The pair (L, μ_{Lin}) of Definition 5.4 is a lax monoidal functor, i.e. a W_{Lin}-algebra.

Proof. Since coherence is identical to that in Proposition 4.5, it will suffice to show functoriality. Let Φ = (X, Y, φ) and Ψ = (Y, Z, ψ) be wiring diagrams with composition Ψ ∘ Φ = (X, Z, ω). We now rewrite \overline{ω} using a matrix equation in terms of \overline{φ} and \overline{ψ} by recasting (5) in matrix form below.

\begin{aligned}\overline{ω} = [\begin{matrix}\overline{ω^{X,X}} & \overline{ω^{X,Z}} \\ \overline{ω^{Z,X}} & \overline{ω^{Z,Z}} \end{matrix}] & = [\begin{matrix}\overline{φ}^{X,Y} & 0 \\ 0 & I \end{matrix}] \overline{ψ} [\begin{matrix}\overline{φ}^{Y,X} & 0 \\ 0 & I \end{matrix}] + [\begin{matrix}\overline{φ}^{X,X} & 0 \\ 0 & 0 \end{matrix}] \\ & = [\begin{matrix}\overline{φ}^{X,Y} \overline{ψ}^{Y,Y} \overline{φ}^{Y,X} + \overline{φ}^{X,X} & \overline{φ}^{X,Y} \overline{ψ}^{Y,Z} \\ \overline{ψ}^{Z,Y} \overline{φ}^{Y,X} & 0 \end{matrix}] \end{aligned}  (14)

We now prove that L(Ψ ∘ Φ) = L(Ψ) ∘ L(Φ). We immediately have L(Ψ ∘ Φ)S = S = L(Ψ)(L(Φ)S). Let h := L(Ψ ∘ Φ)f and k := L(Ψ)(L(Φ)f). We must show h = k. Let g = L(Φ)f and Ψ ∘ Φ = (X, Z, ω). It is then straightforward matrix arithmetic to see that

\begin{aligned}k = L(Ψ)g & = [\begin{matrix}g^{S,Y} & 0 \\ 0 & I \end{matrix}] \overline{ψ} [\begin{matrix}g^{Y,S} & 0 \\ 0 & I \end{matrix}] + [\begin{matrix}g^{S,S} & 0 \\ 0 & 0 \end{matrix}] \\ & = [\begin{matrix}f^{S,X}(\overline{φ}^{X,Y} \overline{ψ}^{Y,Y} \overline{φ}^{Y,X} + \overline{φ}^{X,X})f^{X,S} + f^{S,S} & f^{S,X} \overline{φ}^{X,Y} \overline{ψ}^{Y,Z} \\ \overline{ψ}^{Z,Y} \overline{φ}^{Y,X}f^{X,S} & 0 \end{matrix}] \\ & = [\begin{matrix}f^{S,X} & 0 \\ 0 & I \end{matrix}] \overline{ω} [\begin{matrix}f^{X,S} & 0 \\ 0 & I \end{matrix}] + [\begin{matrix}f^{S,S} & 0 \\ 0 & 0 \end{matrix}] = L(Ψ ∘ Φ)f = h \end{aligned}  (15)

Therefore, the pair (L, μ_{Lin}) constitutes a lax monoidal functor W_{Lin} → Set, i.e., a W_{Lin}-algebra.

5.6. Remark. Although we’ve been referring to L as a subalgebra of G, this is technically not the case since they have different source categories. The following diagram illustrates precisely the relationship between the W_{Lin}-algebra L, defined above, and the W-algebra G, defined in Section 4.

[figure: W_{Lin}; W_{i}; L; ϵ_{⟹}; W; G; Set]  (16)

Here, the natural inclusion W_{i}: W_{Lin} ↪ W corresponds to i: Lin ↪ Man, and we have a natural transformation ϵ: L → G ∘ i. Hence for each X ∈ Ob W_{Lin}, we have a function ϵ_{X}: L(X) → G(i(X)) = G(X) that sends the linear open system (S, f) ∈ L(X) to the open system (TFS_{i}(S), i(f)) = (S, f) ∈ G(X).

As promised, we now reformulate Example 1.2 in terms of our language.

Y Y_{a}^{in} Y_{b}^{in} Y_{a}^{out} X_{1} Q_{1}(t) oz salt 30 gal water X_{1a}^{in} X_{1b}^{in} X_{1a}^{out} X_{2} Q_{2}(t) oz salt 20 gal water X_{2a}^{in} X_{2b}^{in} X_{2a}^{out} X_{2b}^{out} 3 gal/min 1.5 gal/min 1 oz/gal 1 gal/min 3 oz/gal 2.5 gal/min 1.5 gal/min

Figure 9: A dynamical system from Boyce and DiPrima interpreted over a wiring diagram Φ = (X_{1}, X_{2}; Y; φ) in OW.

5.7. Example. For the reader’s convenience, we reproduce Figure 1 and Table 3.

w ∈ X^{in} + Y^{out} X_{1a}^{in} X_{1b}^{in} X_{2a}^{in} X_{2b}^{in} Y_{a}^{out} ; φ(w) ∈ X^{out} + Y^{in} Y_{b}^{in} X_{2b}^{out} Y_{a}^{in} X_{1a}^{out} X_{2a}^{out}

Table 4

We can invoke the yoga of Definition 5.2 to write \overline{φ} as a matrix below:

[ \overline{X_{1a}^{out}} ; \overline{X_{2a}^{out}} ; \overline{X_{2b}^{out}} ; \overline{Y_{a}^{in}} ; \overline{Y_{b}^{in}}] = [\begin{matrix}0 & 0 & I & 0 & 0 \\ 0 & 0 & 0 & 0 & I \\ 0 & I & 0 & 0 & 0 \\ I & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & I & 0 \end{matrix}] [ \overline{X_{1a}^{in}} ; \overline{X_{1b}^{in}} ; \overline{X_{2a}^{in}} ; \overline{X_{2b}^{in}} ; \overline{Y_{a}^{out}}]  (17)

One can think of \overline{φ} as a block permutation matrix consisting of identity and zero matrix blocks. An identity matrix in block entry (i, j) represents the fact that the port whose state space corresponds to row i and the one whose state space corresponds to column j get linked by Φ. In general, the dimension of each I is equal to the dimension of the corresponding state space and hence the formula in (17) is true, independent of the typing. In the specific example of this system, however, all of these ports are typed in ℝ, and so we have I = 1 in (17).

As promised in Example 4.1, we now write the open systems for the X_{i} in Figure 1 as elements of L(X_{i}). The linear open systems below in (18) represent f_{1} and f_{2}, respectively.

[ Q̇_{1} ; X_{1a}^{out} ] = [\begin{matrix}−.1 & 1 & 1 \\ .1 & 0 & 0 \end{matrix}] [ \begin{matrix}Q_{1} \\ X_{1a}^{in} \\ X_{1b}^{in} \end{matrix} ] , [ Q̇_{2} ; X_{2a}^{out} ; X_{2b}^{out} ] = [\begin{matrix}−.2 & 1 & 1 \\ .125 & 0 & 0 \\ .075 & 0 & 0 \end{matrix}] [ \begin{matrix}Q_{2} \\ X_{2a}^{in} \\ X_{2b}^{in} \end{matrix} ]  (18)

Note the proportion of zeros and ones in the f-matrices of (18)—this is perhaps why the making explicit of these details was an afterthought in (9). Because we may have arbitrary nonconstant coefficients, our formalism can capture more intricate systems.

We then use (17) to establish that X_{1b}^{in} = X_{2b}^{out} and X_{2b}^{in} = X_{1a}^{out}. This allows us to recover the equations in (9):

\{ \begin{matrix}Q̇_{1} = −.1Q_{1} + X_{1a}^{in} + X_{1b}^{in} = −.1Q_{1} + 1.5 + X_{2b}^{out} = −.1Q_{1} + .075Q_{2} + 1.5 \\ Q̇_{2} = −.2Q_{2} + X_{2a}^{in} + X_{2b}^{in} = −.2Q_{2} + 3 + X_{1a}^{out} = −.2Q_{2} + .1Q_{1} + 3 \end{matrix}

The coherence map in Definition 5.4 gives us the combined tank system:

(Q, f) := μ_{Lin}(({Q_{1}}, f_{1}), ({Q_{2}}, f_{2})) = ({Q_{1}, Q_{2}}, f_{1} × f_{2}) ∈ L(X).

This system can then be written out as a matrix below

[ Q̇_{1} ; Q̇_{2} ; X_{1a}^{out} ; X_{2a}^{out} ; X_{2b}^{out}] = [\begin{matrix}−.1 & 0 & 1 & 1 & 0 & 0 \\ 0 & −.2 & 0 & 0 & 1 & 1 \\ .1 & 0 & 0 & 0 & 0 & 0 \\ 0 & .125 & 0 & 0 & 0 & 0 \\ 0 & .075 & 0 & 0 & 0 & 0 \end{matrix}] [\begin{matrix}Q_{1} \\ Q_{2} \\ X_{1a}^{in} \\ X_{1b}^{in} \\ X_{2a}^{in} \\ X_{2ba}^{in} \end{matrix}]  (19)

Finally, we can apply formula (13) to (19) above to express as a matrix the open system (Q, g) = (Φ)f ∈ L(Y) for the outer box Y.

[ Q̇_{1} ; Q̇_{2} ; Y^{out} ] = [\begin{matrix}−.1 & .075 & 0 & 1 \\ .1 & −.2 & 1 & 0 \\ 0 & 1 & 0 & 0 \end{matrix}] [ \begin{matrix}Q_{1} \\ Q_{2} \\ Y_{a}^{in} \\ Y_{b}^{in} \end{matrix} ]

References

[Aba15] Joseph Abadi. Orthogonal factorization systems on 1- and 2-Cob. In preparation, 2015.

[AMMO10] Rob Arthan, Ursula Martin, Erik A. Mathiesen, and Paulo Oliva. A general framework for sound and complete Floyd-Hoare logics. ACM Trans. Comput. Log., 11(1):Art. 7, 31, 2010.

[Awo10] Steve Awodey. Category Theory, volume 52 of Oxford Logic Guides. Oxford University Press, Oxford, second edition, 2010.

[Bae13] John Baez. The foundations of applied mathematics. ePrint online:

          math.ucr.edu/home/baez/irvine/irvine.pdf, 5 2013.

[BB12] John C. Baez and Jacob Biamonte. A Course on Quantum Techniques for Stochastic Mechanics. ePrint online: www.arXiv.org/abs/1209.3632, 2012.

[BD65] William E. Boyce and Richard C. DiPrima. Elementary Differential Equations and Boundary Value Problems. John Wiley & Sons, Inc., New York-London-Sydney, 1965.

[BS11] J. Baez and M. Stay. Physics, topology, logic and computation: a Rosetta Stone. In New Structures for Physics, volume 813 of Lecture Notes in Phys., pages 95–172. Springer, Heidelberg, 2011.

[Coe13] Bob Coecke. An alternative gospel of structure: order, composition, pro-

cesses. ePrint online: www.arXiv.org/abs/1307.4038, 2013.

[DL] Lee DeVille and Eugene Lerman. Modular dynamical systems on networks. JEMS (to appear). ePrint online: www.arXiv.org/abs/1303.3907.

[DL10] Lee DeVille and Eugene Lerman. Dynamics on networks I. Combinatorial categories of modular continuous-time systems. ePrint online:

www.arXiv.org/abs/1008.5359, 2010.

[DL15] Lee DeVille and Eugene Lerman. Dynamics on networks of manifolds. SIGMA Symmetry Integrability Geom. Methods Appl., 11:Paper 022, 21, 2015.

[Gro13]  Mikhail  Gromov.  In  a  search  for  a  struc-
ture,  part  1:  On  entropy.  ePrint  online:

www.ihes.fr/~gromov/PDF/structre-serch-entropy-july5-2012.pdf, 6

2013.

[JS91] André Joyal and Ross Street. The geometry of tensor calculus. I. Adv. Math., 88(1):55–112, 1991.

[JSV96] André Joyal, Ross Street, and Dominic Verity. Traced monoidal categories. Math. Proc. Cambridge Philos. Soc., 119(3):447–468, 1996.

[KFA69] R. E. Kalman, P. L. Falb, and M. A. Arbib. Topics in Mathematical System Theory. McGraw-Hill Book Co., New York-Toronto, Ont.-London, 1969.

[Koe67] Arthur Koestler. The Ghost in the Machine. Hutchinson & Co., 1967.

[Lei04] Tom Leinster. Higher Operads, Higher Categories, volume 298 of London Mathematical Society Lecture Note Series. Cambridge University Press, Cambridge, 2004.

[ML98] Saunders Mac Lane. Categories for the Working Mathematician, volume 5 of Graduate Texts in Mathematics. Springer-Verlag, New York, second edition, [Sco71] Dana Scott. The lattice of flow diagrams. In Symposium on Semantics of

Algorithmic Languages, pages 311–366. Lecture Notes in Mathematics, Vol.

188. Springer, Berlin, 1971.

[Sel11] P. Selinger. A survey of graphical languages for monoidal categories. In New structures for physics, volume 813 of Lecture Notes in Phys., pages 289–355. Springer, Heidelberg, 2011.

[Spi65] Michael Spivak. Calculus on Manifolds. A Modern Approach to Classical Theorems of Advanced Calculus. W. A. Benjamin, Inc., New York-Amsterdam, 1965.

[Spi13] David I. Spivak. The operad of wiring diagrams: formalizing a graphical language for databases, recursion, and plug-and-play circuits. ePrint online:

          www.arXiv.org/abs/arXiv:1305.0297, 2013.

[Spi14] David I. Spivak. Category Theory for the Sciences. MIT Press, 2014.

[SR13] David I. Spivak and Dylan Rupel. The operad of temporal wiring diagrams: formalizing a graphical language for discrete-time processes. ePrint online:

          www.arXiv.org/abs/1307.6894, 2013.

[SSR15] David I. Spivak, Patrick Schultz, and Dylan Rupel. Traced categories as lax functors out of free compact categories. (In preparation), 2015.

[Tes12] Gerald Teschl. Ordinary Differential Equations and Dynamical Systems, volume 140 of Graduate Studies in Mathematics. American Mathematical Society, Providence, RI, 2012.

[War83] Frank W. Warner. Foundations of Differentiable Manifolds and Lie Groups, volume 94 of Graduate Texts in Mathematics. Springer-Verlag, New York-Berlin, 1983. Corrected reprint of the 1971 edition.

Duke University Mathematics Department Box 90320 Durham, NC 27708-0320

Massachusetts Institute of Technology Department of Mathematics, E17-332 77 Massachusetts Avenue Cambridge, MA 02139-4307

Mathematics Department University of Illinois at Urbana-Champaign 1409 W. Green Street Urbana, Illinois 61801-2975

Email: dv@math.duke.edu
      dspivak@math.mit.edu
      lerman@math.uiuc.edu
This article may be accessed at http://www.tac.mta.ca/tac/

THEORY AND APPLICATIONS OF CATEGORIES (ISSN 1201-561X) will disseminate articles that significantly advance the study of categorical algebra or methods, or that make significant new contributions to mathematical science using categorical methods. The scope of the journal includes: all areas of pure category theory, including higher dimensional categories; applications of category theory to algebra, geometry and topology and other areas of mathematics; applications of category theory to computer science, physics and other mathematical sciences; contributions to scientific knowledge that make use of categorical methods. Articles appearing in the journal have been carefully and critically refereed under the responsibility of members of the Editorial Board. Only papers judged to be both significant and excellent are accepted for publication. Full text of the journal is freely available from the journal’s server at http://www.tac.mta.ca/tac/. It is archived electronically and in printed paper format.

Subscription information Individual subscribers receive abstracts of articles by e-mail as they are published. To subscribe, send e-mail to tac@mta.ca including a full name and postal address. For institutional subscription, send enquiries to the Managing Editor, Robert Rosebrugh, rrosebrugh@mta.ca.

Information for authors The typesetting language of the journal is TEX, and L^{A}TEX2e is required. Articles in PDF format may be submitted by e-mail directly to a Transmitting Editor. Please obtain detailed information on submission format and style files at http://www.tac.mta.ca/tac/.

Managing editor. Robert Rosebrugh, Mount Allison University: rrosebrugh@mta.ca

TEXnical editor. Michael Barr, McGill University: barr@math.mcgill.ca

Assistant TEX editor. Gavin Seal, Ecole Polytechnique Fédérale de Lausanne:

gavin seal@fastmail.fm

Transmitting editors.

Clemens Berger, Université de Nice-Sophia Antipolis: cberger@math.unice.fr Richard Blute, Université d’ Ottawa: rblute@uottawa.ca Lawrence Breen, Université de Paris 13: breen@math.univ-paris13.fr Ronald Brown, University of North Wales: ronnie.profbrown(at)btinternet.com Valeria de Paiva: Nuance Communications Inc: valeria.depaiva@gmail.com Ezra Getzler, Northwestern University: getzler(at)northwestern(dot)edu Kathryn Hess, Ecole Polytechnique Fédérale de Lausanne: kathryn.hess@epfl.ch Martin Hyland, University of Cambridge: M.Hyland@dpmms.cam.ac.uk Anders Kock, University of Aarhus: kock@imf.au.dk Stephen Lack, Macquarie University: steve.lack@mq.edu.au F. William Lawvere, State University of New York at Buffalo: wlawvere@buffalo.edu Tom Leinster, University of Edinburgh: Tom.Leinster@ed.ac.uk Ieke Moerdijk, Radboud University Nijmegen: i.moerdijk@math.ru.nl Susan Niefield, Union College: niefiels@union.edu Robert Paré, Dalhousie University: pare@mathstat.dal.ca Jiri Rosicky, Masaryk University: rosicky@math.muni.cz Giuseppe Rosolini, Università di Genova: rosolini@disi.unige.it Alex Simpson, University of Ljubljana: Alex.Simpson@fmf.uni-lj.si James Stasheff, University of North Carolina: jds@math.upenn.edu Ross Street, Macquarie University: street@math.mq.edu.au Walter Tholen, York University: tholen@mathstat.yorku.ca Myles Tierney, Université du Québec à Montréal : tierney.myles4@gmail.com R. J. Wood, Dalhousie University: rjwood@mathstat.dal.ca