Skip to the Main Content

Note:These pages make extensive use of the latest XHTML and CSS Standards. They ought to look great in any standards-compliant modern browser. Unfortunately, they will probably look horrible in older browsers, like Netscape 4.x and IE 4.x. Moreover, many posts use MathML, which is, currently only supported in Mozilla. My best suggestion (and you will thank me when surfing an ever-increasing number of sites on the web which have been crafted to use the new standards) is to upgrade to the latest version of your browser. If that's not possible, consider moving to the Standards-compliant and open-source Mozilla browser.

August 1, 2022

Timing, Span(Graph) and Cospan(Graph)

Posted by Emily Riehl

Guest post by Siddharth Bhat and Pim de Haan. Many thanks to Mario Román for proofreading this blogpost.

This paper explores modelling automata using the Span/Cospan framework by Sabadini and Walters. The aim of this blogpost is to introduce the key constructions that are used in this paper, and to explain how these categorical constructions allow us to talking about modelling automata and timing in these automata.

The category Span(C)Span(C)

The category Span(C)Span(C) is built from the category CC by considering diagrams of the form LARL \leftarrow A \rightarrow R, where AA is the apex of the span, and L,RL, R are the base of the span. The ordering of left and right is important when we describe the composition of spans. Formally, the objects of Span(C)Span(C) are the objects of CC. The arrows of Span(C)Span(C) are from AA to BB are spans (AfXgBA \xleftarrow{f} X \xrightarrow{g} B).

Now, a natural question is to ask how one composes spans. We compose spans by taking their pullback. Consequently, the category Span(C)Span(C) only exists if CC has all pullbacks. The composition of a span (AfXgBA \xleftarrow{f} X \xrightarrow{g} B) with another (BhYkCB \xleftarrow{h} Y \xrightarrow{k} C) is given by the pullback X× BYX \times_B Y with the associated diagram:

composition of spans

Some examples of spans follows:

  • First, as mathematicians, we are honor-bound to give the trivial example (ArmidArmidAA \xleftarrow{\rm id} A \xrightarrow{\rm id} A) is the identity span on the object AA.

  • Next, any arrow f:AAf: A \to A' can be considered as a span on the left (AfArmidAA' \xleftarrow{f'} A \xrightarrow{\rm id} A'), or as a span to the right (ArmidAfAA \xleftarrow{\rm id} A \xrightarrow{f} A'). Note that these define a pair of functors from CC to Span(C)Span(C).

A prototypical example of spans is the span of two finite sets. Suppose we have two sets A,BA, B, and we wish to describe the set of ways to go from AA to BB (where we think of AA and BB as abstract locations). In such a case, we need a set SS, which describes the set of ways to get from AA to BB, and morphisms π A:SA\pi_A: S \to A, π B:SB\pi_B: S \to B that gives us the start and end position of a path from some element of AA to some element of BB.

Remark The pullback, and thus the composition of spans, is only unique up to isomorphism. Hence, Span(C)Span(C) is only a proper category if the morphisms are taken to be the isomorphism classes of spans.

The category GraphGraph of directed multigraphs

There are many slightly different notions of a graph in the literature. For our exposition, we will focus on the category of directed multigraphs. Intuitively, this means that we have vertices (states of an automata) and edges (transitions). There can be multiple edges between a pair of vertices (there are multiple ways to transition from one state into another).

Formally, a multigraph is given by a vertex set VV, a set of edges EE and a pair functions s,t:EVs, t: E \to V which denote the source and target of the edge. We will denote a graph as G(V,E)G \equiv (V, E) as a pair of its vertex and edge set. We denote V(G)V(G) for the vertex set of GG, and E(G)E(G) for the edge set of GG.

The objects of the category GraphGraph are these directed multigraphs. The arrows of this category are multigraph morphisms.

A morphism f:GHf: G \to H in this category is given by two set valued functions f V:V(G)V(H)f_V: V(G) \to V(H) which maps vertices, and f E:E(G)E(H)f_E: E(G) \to E(H) which maps edges, under the condition that the images of the edges are consistent with the images of the vertices. That is, for all eE(G)e \in E(G), s(f E(e))=f V(s(e))s(f_E(e))=f_V(s(e)) and t(f E(e))=f V(t(e))t(f_E(e))=f_V(t(e)). Said differently, the above condition means that edges must preserve adjacency.

Remark A more concise way to define the above construction is as the presheaf category [Arr op,Set][Arr^{op}, Set], over the diagram Arr=(Vs,tE)Arr=(V \xrightarrow{s, t} E), whose objects are functors G:Arr opSetG: Arr^{op} \to Set and morphisms are natural transformations.

The (co)limits of GraphGraph

The category of graphs has products X×YX \times Y, which is computed pointwise: E(X×Y)=E(X)×E(Y)E(X \times Y)=E(X) \times E(Y) and V(X×Y)=V(X)×V(Y)V(X \times Y)=V(X) \times V(Y). Similarly, it has coproducts X+YX+Y, also computed pointwise. GraphGraph can thus be made into a cartesian monoidal category (Graph,=×,I=())(Graph, \otimes=\times, I=(\star \to \star)) or a cocartesian category (Graph,=+,I=)(Graph, \otimes=+, I=\emptyset).

The pullback of a diagram of graphs XfZgYX \xrightarrow{f} Z \xleftarrow{g} Y, written X× ZYX \times_Z Y, intuitively performs a pullback along the vertices and the edges. Formally, it is a graph X× ZYX \times_Z Y whose vertex set is the pullback of the vertices: V(X× ZY){(v,v):vV(X),vV(Y),f V(v)=g V(v)}V(X \times_Z Y) \equiv \{ (v, v') : v \in V(X), v' \in V(Y), f_V(v) = g_V(v') \}, and whose edge set is the pullback of the edges: E(X× ZY){(e,e):eE(X),eE(Y),f E(e)=g E(e)}E(X \times_Z Y) \equiv \{ (e, e') : e \in E(X), e' \in E(Y), f_E(e) = g_E(e') \}.

The pushout dualizes the above construction. Intuitively, it glues two graphs along a third one. Formally, the pushout of a diagram of graphs XfZgYX \xleftarrow{f} Z \xrightarrow{g} Y, written X+ ZYX +_Z Y, is a quotient X+Y/X+Y/\sim by the equivalence generated by f V(v)g Z(v),vV(Z),f E(e)g E(e),eE(Z)f_V(v) \sim g_Z(v), v \in V(Z), f_E(e) \sim g_E(e), e \in E(Z).

Remark Seeing GraphGraph as the functor category [Arr op,Set][Arr^{op}, Set], GraphGraph automatically derives the above limits and colimits from SetSet. The (co)limits are then computed pointwise.

Parallel composition of automata with Span(Graph)Span(Graph)

At this stage, we have the machinery necessary to add labels onto our graph edges, by means of exploiting Span(Graph)Span(Graph), which is a category as GraphGraph has pullbacks. Span(Graph)Span(Graph) is a symmetric monoidal category with the monoidal product deriving from the cartesian monoidal structure on GraphGraph.

In our case, for automata, we focus on the situation where the graphs at the base are graphs with a single vertex and many edges. These edges are thought of as transition labels. Formally, for a given set of labels AA, we create the graph (A)(,A)\mathcal{E}(A) \equiv (\star, A).

An automaton is then a span (A)fGg(B)\mathcal{E}(A) \xleftarrow{f} G \xrightarrow{g} \mathcal{E}(B). The states of the automaton are the vertices V(G)V(G) and the transitions the edges E(G)E(G). By definition, each transition eE(G)e \in E(G) maps to some edge a=f E(e)E((A))=Aa=f_E(e) \in E(\mathcal{E}(A))=A and some edge b=g E(e)E((B))=Bb=g_E(e) \in E(\mathcal{E}(B))=B. We denote this diagramatically as a label a/ba/b on the transition.

When composing spans (A)G(B)G(C)\mathcal{E}(A) \leftarrow G \rightarrow \mathcal{E}(B)\leftarrow G' \rightarrow \mathcal{E}(C), we get (A)G× (B)G(C)\mathcal{E}(A) \leftarrow G \times_{\mathcal{E}(B)} G' \rightarrow \mathcal{E}(C). This composition can be interpreted as synchronized parallel computation. The pullback contains all vertices V(G)×V(G)V(G) \times V(G'), meaning that the state (v,v)(v,v') of the composed automaton is a product of both a state vv of automaton GG and a state vv' of automaton GG'. For the transitions, however, only the edges (e,e)(e, e') that have the same BB label survive. This can be interpreted as a requirement that automata GG and GG' communicate and can only transition when their BB signal agrees.

Sequential composition of automata with Copan(Graph)Copan(Graph)

In the exact same way that Span(Graph)Span(Graph) provides us with parallel composition, dualising the construction to Cospan(Graph)Cospan(Graph) gives us sequential composition. This is a category whose objects are graphs, morphisms are cospans XZYX \rightarrow Z \leftarrow Y of graphs and composition is given by pushout, which exist for GraphGraph. Cospan(Graph)Cospan(Graph) is a symmetric monoidal category due to the cocartesian monoidal structure on GraphGraph.

For a set AA, define the graph 𝒱(A)(A,)\mathcal{V}(A)\equiv(A,\emptyset) to contain no edges. Then a cospan 𝒱(A)G𝒱(B)\mathcal{V}(A) \to G \leftarrow \mathcal{V}(B) can be interpreted as an automaton with states V(G)V(G) and edges E(G)E(G) having AA input states, with each aAa \in A corresponding to a state vV(G)v \in V(G), and similarly BB output states.

A composition of cospans 𝒱(A)G(B)G(C)\mathcal{V}(A) \rightarrow G \leftarrow \mathcal{E}(B)\rightarrow G' \leftarrow \mathcal{E}(C) of automata yields a new automaton 𝒱(A)G+ 𝒱(B)G𝒱(C)\mathcal{V}(A) \rightarrow G +_{\mathcal{V}(B)} G' \leftarrow \mathcal{V}(C). This composition can be thought of as sequential computation, as the state of the composed automaton is either a state vv of GG or a state vv' of GG', where we glue toghether output and inputs states, because we make the equivalence that vvv \sim v' if vv corresponds to an output bBb \in B that corresponds as an input to vv'.

Wiring in Span(Graph)

Composition in Span(Graph) allows one to compose spans XGYGZX \leftarrow G \rightarrow Y \leftarrow G' \rightarrow Z into a span between XX and ZZ, while the tensor product of spans XGY,XGYX \leftarrow G \rightarrow Y, X' \leftarrow G' \rightarrow Y' yield a span between X×XX \times X' and Y×YY \times Y'. However, to allow for more flexible compositions, such as the composition of spans XGY,XGZX \leftarrow G \rightarrow Y, X \leftarrow G' \rightarrow Z into a span between XX and Y×ZY \times Z, one needs morphisms to connect multiple copies of XX. In a string diagram of Span(Graph)Span(Graph) this looks like:

Example of using the Frobenius monoid

As automata, this corresponds to a synchronization between the parallel processes GG and GG', so that they can transition when their left XX transition is equal. Generally, such connectors between parallel XX interfaces of automata are given by a Frobenius monoid on XX, which consists of the following spans: - X×XΔXrmidXX \times X \xleftarrow{\Delta} X \xrightarrow{\rm id} X, giving μ X:X×XXSpan(Graph)\mu_X : X \times X \to X \in Span(Graph) - I!XrmidXI \xleftarrow{!} X \xrightarrow{\rm{id}} X, giving η X:IXSpan(Graph)\eta_X : I \to X \in Span(Graph) - XrmidXΔX×XX \xleftarrow{\rm{id}} X \xrightarrow{\Delta} X \times X, giving δ X:XX×XSpan(Graph)\delta_X : X \to X \times X \in Span(Graph) - XrmidX!IX \xleftarrow{\rm{id}} X \xrightarrow{!} I, giving ϵ X:XISpan(Graph)\epsilon_X : X \to I \in Span(Graph)

where we use the following morphisms in GraphGraph: - !:XI!: X \to I, where the monoidal unit II is the terminal graph with a single vertex and single loop. - Δ:XX×X\Delta: X \to X \times X that is the identity on the components. Concretely on graphs, it maps vertex vv to (v,v)(v,v) and edge ee to (e,e)(e,e).

These are written as string diagrams in Span(Graph)Span(Graph) [figs from Fong & Spivak 2019] Frobenius monoid morphisms

It can be shown that these obey the commutative monoid axioms

Monoid axioms

the cocommutative comonoid axioms

Comonoid axioms and the Frobenius and special axioms

Frobenius axioms

Definition. A tuple (X,μ X,η X,δ X,ϵ X)(X, \mu_X, \eta_X, \delta_X, \epsilon_X) of such maps satisfying these axioms is called a special commutative Frobenius monoid.

Theorem. [Fong & Spivak 2018] Given a special commutative Frobenius monoid (X,μ X,η X,δ X,ϵ X)(X, \mu_X, \eta_X, \delta_X, \epsilon_X), for two non-negative integers m,nm, n, any map X mX nX^{\otimes m} \to X^{\otimes n} composed of μ X,η X,δ X,ϵ X\mu_X, \eta_X, \delta_X, \epsilon_X and the swap σ X\sigma_X, whose string diagram is connected, equals the spider morphism s n,ms_{n,m} given by

Spider composition

which is also written as

Spider symbol

If a special commutative Frobenius monoid exist for all objects in a category and the Frobenius monoid for tensor products XYX \otimes Y are composed of the Frobenius monoid of the objects XX and YY, then the category is called hypergraph category [Fong & Spivak 2019]. String diagrams of such categories can be interpreted as a hypergraph. A hypergraph is a graph in which the edges connect an arbitrary number of nodes. In this case, the spans are the nodes of the hypergraph and the spider morphisms form the hyperedges.

Remark The fact that Span(Graph)Span(Graph) is a hypergraph category relies on the fact that GraphGraph is a Cartesian category, a symmetric monoidal category whose tensor product is a categorical product and whose unit is terminal. Hence, for any Cartesian category CC, Span(C)Span(C) is a hypergraph category. The spans in the Frobenius monoids are constructed similarly from the diagonal morphisms Δ:XX×X\Delta: X \to X \times X and terminal maps !:XI! : X \to I.

Wiring in Cospan(Graph)

Similar to Span(Graph)Span(Graph), Cospan(Graph)Cospan(Graph) also forms a hypergraph category in which each object is equiped with a spider morphism. Recall that GraphGraph is a symmetric monoidal category with as tensor product \otimes the disjoint union ++ of graphs, which is a coproduct, and its unit is II, the initial graph \emptyset, which contains no edges and vertices. As such, it is equiped with a codiagonal map :X+XX\nabla: X + X \to X, which is the identity on each part, and an initial map !:IX!: I \to X. For any graph XX, one can construct the following cospans, constituting a special Frobenius monoid: - X+XXrmidXX + X \xrightarrow{\nabla} X \xleftarrow{\rm id} X, giving μ X:X+XXCospan(Graph)\mu_X : X+X \to X \in Cospan(Graph) - I!XrmidXI \xrightarrow{!} X \xrightarrow{\rm{id}} X, giving η X:IXCospan(Graph)\eta_X : I \to X \in Cospan(Graph) - XrmidXXXX \xrightarrow{\rm{id}} X \xleftarrow{\nabla} X \otimes X, giving δ X:XXXCospan(Graph)\delta_X : X \to X \otimes X \in Cospan(Graph) - XrmidX!IX \xrightarrow{\rm{id}} X \xleftarrow{!} I, giving ϵ X:XICospan(Graph)\epsilon_X : X \to I \in Cospan(Graph)

Remark In more generality, for any cocartesian category CC - a symmetric monoidal category whose tensor product is a coproduct and unit is initial - Cospan(C)Cospan(C) is a hypergraph category.

Feedback via traces

Some automata may also want to synchronize their parallel left and right interfaces (in the case of Span(Graph)Span(Graph)) or their sequential top and bottom interfaces (in the case of Cospan(Graph)Cospan(Graph)). In either case, the hypergraph structure provides for this in the following way:


Hence, every hypergraph category HH is traced monoidal category, which are categories which provide a notion of feedback by providing for all objects X,Y,ZX, Y, Z, a tracing map: Tr X,Y Z:H(XZ,YZ)H(X,Y) Tr^Z_{X,Y} : H(X \otimes Z, Y \otimes Z) \to H(X, Y) satisfying some coherence axioms.


A path in a directed graph is a sequence of edges (e 0,e 1,...)(e_0, e_1, ...) such that the tail node of edge e ie_i equals the start node of edge e i+1e_{i+1}. In the context of an automaton, a path is called a behaviour. The automaton can be interpreted as a discrete time system, in the simplest case by saying that each edge has time duration 1, so that the duration of a behaviour equals the length of the path. Note that this notion of time is imposed as an interpretation, while the underlying model remains unchanged.

As an example, we will construct a clock by parallel composing automata that cycle with frequency 1, 60, 60 and 24. We define one parallel interface X={s,ϵ,}X = \{s, \epsilon,\}, corresponding to taking a step or remaining idle. We define an automaton TT with left interface !={}!= \{\star\} and right interface XX with one node and one edge: 1/s11 \xrightarrow{\star/ s} 1. This automaton sends a tick to the right at each step. Also, for any natural number tt, we define automaton G tG_t with left and right interface XX:

Clock hand

Whenever G tG_t receives a tick from the left, it ticks itself. After tt ticks, it sends a tick to the right.

If we compose these automata as:


We get a unit interface on the left and interface X×X×X×XX \times X \times X \times X on the right. Its only behaviour is a single cycle of duration 16060241 \cdot 60 \cdot 60 \cdot 24. The right labels are ss on the first position on each step, ss on the second position every 60 steps, ss on the third position every 606060 \cdot 60 steps and ss on the fourth position every 60602460 \cdot60 \cdot 24 steps. We have built a clock.


  • Baez, John C. “Spans in quantum theory.” Keynote talk at Deep Beauty: Mathematical Innovation and the Search for an Underlying Intelligibility of the Quantum World, Princeton University
  • Alessandra Cherubini, Nicoletta Sabadini, Robert F. C. Walters: Timing in the Cospan-Span Model. Electron. Notes Theor. Comput. Sci. 104: 81-97 (2004)
  • Brendan Fong and David I. Spivak. 2019. “Hypergraph Categories.” Journal of Pure and Applied Algebra 223 (11): 4746-77.
  • Brendan Fong and David I. Spivak. 2018. “Seven Sketches in Compositionality: An Invitation to Applied Category Theory.”
Posted at August 1, 2022 9:35 PM UTC

TrackBack URL for this Entry:

0 Comments & 0 Trackbacks

Post a New Comment