Algebraic Let the
Kleene star X^\star denote the
free monoid, i.e. the set of lists with elements in a set X . A
monoidal signature \Sigma is given by: • a set \Sigma_0 of
generating objects, the lists of generating objects in \Sigma_0^\star are also called
types, • a set \Sigma_1 of
generating arrows, also called
boxes, • a pair of functions \text{dom}, \text{cod} : \Sigma_1 \to \Sigma_0^\star which assign a
domain and
codomain to each box, i.e. the input and output types. A morphism of monoidal signature F : \Sigma \to \Sigma' is a pair of functions F_0 : \Sigma_0 \to \Sigma'_0 and F_1 : \Sigma_1 \to \Sigma'_1 which is compatible with the domain and codomain, i.e. such that \text{dom} \circ F_1 \ = \ F_0 \circ \text{dom} and \text{cod} \circ F_1 \ = \ F_0 \circ \text{cod} . Thus we get the category \mathbf{MonSig} of monoidal signatures and their morphisms. There is a
forgetful functor U : \mathbf{MonCat} \to \mathbf{MonSig} which sends a monoidal category to its underlying signature and a
monoidal functor to its underlying morphism of signatures, i.e. it forgets the identity, composition and tensor. The
free functor C_- : \mathbf{MonSig} \to \mathbf{MonCat} , i.e. the
left adjoint to the forgetful functor, sends a monoidal signature \Sigma to the
free monoidal category C_\Sigma it generates. String diagrams (with generators from \Sigma) are arrows in the free monoidal category C_\Sigma. The interpretation in a monoidal category D is a defined by a monoidal functor F : C_\Sigma \to D, which by freeness is uniquely determined by a morphism of monoidal signatures F : \Sigma \to U(D). Intuitively, once the image of generating objects and arrows are given, the image of every diagram they generate is fixed.
Geometric A
topological graph, also called a one-dimensional
cell complex, is a tuple (\Gamma, \Gamma_0, \Gamma_1) of a
Hausdorff space \Gamma , a
closed discrete subset \Gamma_0 \subseteq \Gamma of
nodes and a set of
connected components \Gamma_1 called
edges, each homeomorphic to an open interval with boundary in \Gamma_0 and such that \Gamma - \Gamma_0 = \coprod \Gamma_1 . A
plane graph between two real numbers a, b \in \mathbb{R} with a is a finite topological graph embedded in \mathbb{R} \times [a, b] such that every point x \in \Gamma \ \cap \ \mathbb{R} \times \{ a, b \} is also a node x \in \Gamma_0 and belongs to the closure of exactly one edge in \Gamma_1 . Such points are called
outer nodes, they define the
domain and '''codomain \text{dom}(\Gamma), \text{cod}(\Gamma) \in \Gamma_1^\star ''' of the string diagram, i.e. the list of edges that are connected to the top and bottom boundary. The other nodes f \in \Gamma_0 \ - \ \{ a, b \} \times \mathbb{R} are called
inner nodes. A plane graph is
progressive, also called
recumbent, when the vertical projection e \to [a, b] is injective for every edge e \in \Gamma_1 . Intuitively, the edges in a progressive plane graph go from top to bottom without bending backward. In that case, each edge can be given a top-to-bottom orientation with designated nodes as source and target. One can then define the domain and codomain '''\text{dom}(f), \text{cod}(f) \in \Gamma_1^\star
of each inner node f ''', given by the list of edges that have source and target. A plane graph is
generic when the vertical projection \Gamma_0 - \{ a, b \} \times \mathbb{R} \to [a, b] is injective, i.e. no two inner nodes are at the same height. In that case, one can define a list \text{boxes}(\Gamma) \in \Gamma_0^\star of the inner nodes ordered from top to bottom. A progressive plane graph is
labeled by a monoidal signature \Sigma if it comes equipped with a pair of functions v_0 : \Gamma_1 \to \Sigma_0 from edges to generating objects and v_1 : \Gamma_0 - \{ a, b \} \times \mathbb{R} \to \Sigma_1 from inner nodes to generating arrows, in a way compatible with domain and codomain. A
deformation of plane graphs is a
continuous map h : \Gamma \times [0, 1] \to [a, b] \times \mathbb{R} such that • the image of h(-, t) defines a plane graph for all t \in [0, 1] , • for all x \in \Gamma_0 , if h(x, t) is an inner node for some t it is inner for all t \in [0, 1] . A deformation is progressive (generic, labeled) if h(-, t) is progressive (generic, labeled) for all t \in [0, 1] . Deformations induce an equivalence relation with \Gamma \sim \Gamma' if and only if there is some h with h(-, 0) = \Gamma and h(-, 1) = \Gamma' . String diagrams are
equivalence classes of labeled progressive plane graphs. Indeed, one can define: • the identity diagram \text{id}(x) as a set of parallel edges labeled by some type x \in \Sigma_0^\star, • the composition of two diagrams as their vertical concatenation with the codomain of the first identified with the domain of the second, • the tensor of two diagrams as their horizontal concatenation.
Combinatorial While the geometric definition makes explicit the link between
category theory and
low-dimensional topology, a
combinatorial definition is necessary to formalise string diagrams in
computer algebra systems and use them to define
computational problems. One such definition is to define string diagrams as equivalence classes of well-typed formulae generated by the signature, identity, composition and tensor. In practice, it is more convenient to encode string diagrams as formulae in
generic form, which are in bijection with the labeled generic progressive plane graphs defined above. Fix a monoidal signature \Sigma. A
layer is defined as a triple (x, f, y) \in \Sigma_0^\star \times \Sigma_1 \times \Sigma_0^\star =: L(\Sigma) of a type x on the left, a box f in the middle and a type y on the right. Layers have a domain and codomain \text{dom}, \text{cod} : L(\Sigma) \to \Sigma_0^\star defined in the obvious way. This forms a
directed multigraph, also known as a
quiver, with the types as vertices and the layers as edges.
A string diagram d is encoded as a path in this multigraph, i.e. it is given by: • a domain \text{dom}(d) \in \Sigma_0^\star as starting point • a length \text{len}(d) = n \geq 0, • a list of \text{layers}(d) = d_1 \dots d_n \in L(\Sigma) such that \text{dom}(d_1) = \text{dom}(d) and \text{cod}(d_i) = \text{dom}(d_{i+1}) for all i . In fact, the explicit list of layers is redundant, it is enough to specify the length of the type to the left of each layer, known as the
offset. The
whiskering d \otimes z of a diagram d = (x_1, f_1, y_1) \dots (x_n, f_n, y_n) by a type z is defined as the concatenation to the right of each layer d \otimes z = (x_1, f_1, y_1 z) \dots (x_n, f_n, y_n z) and symmetrically for the whiskering z \otimes d on the left. One can then define: • the identity diagram \text{id}(x) with \text{len}(\text{id}(x)) = 0 and \text{dom}(\text{id}(x)) = x, • the composition of two diagrams as the concatenation of their list of layers, • the tensor of two diagrams as the composition of whiskerings d \otimes d' = d \otimes \text{dom}(d') \ \circ \ \text{cod}(d) \otimes d'. Note that because the diagram is in generic form (i.e. each layer contains exactly one box) the definition of tensor is necessarily biased: the diagram on the left hand-side comes above the one on the right-hand side. One could have chosen the opposite definition d \otimes d' = \text{dom}(d) \otimes d' \ \circ \ d \otimes \text{cod}(d'). Two diagrams are equal (up to the axioms of monoidal categories) whenever they are in the same equivalence class of the
congruence relation generated by the
interchanger:d \otimes \text{dom}(d') \ \circ \ \text{cod}(d) \otimes d' \quad = \quad \text{dom}(d) \otimes d' \ \circ \ d \otimes \text{cod}(d')That is, if the boxes in two consecutive layers are not connected then their order can be swapped. Intuitively, if there is no communication between two parallel processes then the order in which they happen is irrelevant. The
word problem for free monoidal categories, i.e. deciding whether two given diagrams are equal, can be solved in
polynomial time. The interchanger is a
confluent rewriting system on the subset of
boundary connected diagrams, i.e. whenever the plane graphs have no more than one connected component which is not connected to the domain or codomain and the
Eckmann–Hilton argument does not apply. == Extension to 2-categories ==