String diagrams are a formal graphical language for representing morphisms in monoidal categories, or more generally 2-cells in

2-categories In category theory, a strict 2-category is a category with "morphisms between morphisms", that is, where each hom-set itself carries the structure of a category. It can be formally defined as a category enriched over Cat (the category of catego ...

. They are a prominent tool in

applied category theory Applied category theory is an Discipline (academia), academic discipline in which methods from category theory are used to study other fields including but not limited to computer science, physics (in particular Categorical quantum mechanics, quant ...

. When interpreted in the monoidal category of vector spaces and linear maps with the tensor product, string diagrams are called tensor networks or Penrose graphical notation. This has led to the development of categorical quantum mechanics where the axioms of quantum theory are expressed in the language of monoidal categories.

History

Günter Hotz Günter Hotz (born 16 November 1931) is a German pioneer of computer science. His work includes formal languages, digital circuits and computational complexity theory. In 1987, he received the Gottfried Wilhelm Leibniz Prize of the Deutsche Forschu ...

gave the first mathematical definition of string diagrams in order to formalise

electronic circuit An electronic circuit is composed of individual electronic components, such as resistors, transistors, capacitors, inductors and diodes, connected by conductive wires or traces through which electric current can flow. It is a type of electrical ...

s, but the article remained confidential because of the absence of an English translation. The invention of string diagrams is usually credited to

Roger Penrose Sir Roger Penrose (born 8 August 1931) is an English mathematician, mathematical physicist, philosopher of science and Nobel Laureate in Physics. He is Emeritus Rouse Ball Professor of Mathematics in the University of Oxford, an emeritus fello ...

with Feynman diagrams also described as a precursor. They were later characterised as the arrows of free monoidal categories in a seminal article by André Joyal and

Ross Street Ross Howard Street (born 29 September 1945, Sydney) is an Australian mathematician specialising in category theory.LaTeX and PGF/TikZ made the publication of string diagrams more wide-spread. The existential graphs and diagrammatic reasoning of Charles Sanders Peirce are arguably the oldest form of string diagrams, they are interpreted in the monoidal category of finite sets and

relations Relation or relations may refer to: General uses *International relations, the study of interconnection of politics, economics, and law on a global level *Interpersonal relationship, association or acquaintance between two or more people *Public ...

with the

Cartesian product In mathematics, specifically set theory, the Cartesian product of two sets ''A'' and ''B'', denoted ''A''×''B'', is the set of all ordered pairs where ''a'' is in ''A'' and ''b'' is in ''B''. In terms of set-builder notation, that is : A\ti ...

. The lines of identity of Peirce's existential graphs can be axiomatised as a Frobenius algebra, the cuts are unary operators on homsets that axiomatise

logical negation In logic, negation, also called the logical complement, is an operation that takes a proposition P to another proposition "not P", written \neg P, \mathord P or \overline. It is interpreted intuitively as being true when P is false, and false ...

. This makes string diagrams a sound and

complete Complete may refer to: Logic * Completeness (logic) * Completeness of a theory, the property of a theory that every formula in the theory's language or its negation is provable Mathematics * The completeness of the real numbers, which implies t ...

two-dimensional deduction system for first-order logic, invented independently from the one-dimensional syntax of Gottlob Frege's Begriffsschrift.

Intuition

String diagrams are made of boxes

f : x \to y

, which represent

processes A process is a series or set of activities that interact to produce a result; it may occur once-only or be recurrent or periodic. Things called a process include: Business and management *Business process, activities that produce a specific se ...

, with a list of wires

x

coming in at the top and

y

at the bottom, which represent the input and output

systems A system is a group of interacting or interrelated elements that act according to a set of rules to form a unified whole. A system, surrounded and influenced by its environment, is described by its boundaries, structure and purpose and express ...

being processed by the box

f

. Starting from a collection of wires and boxes, called a signature, one may generate the set of all string diagrams by induction: * each box

f : x \to y

is a string diagram, * for each list of wires

x

, the identity

\text(x) : x \to x

is a string diagram representing the process which does nothing to its input system, it is drawn as a bunch of parallel wires, * for each pair of string diagrams

f : x \to y

and

f' : x' \to y'

, their tensor

f \otimes f' : x x' \to y y'

is a string diagram representing the parallel composition of processes, it is drawn as the horizontal concatenation of the two diagrams, * for each pair of string diagrams

f : x \to y

and

g : y \to z

, their composition

g \circ f : x \to z

is a string diagram representing the sequential composition of processes, it is drawn as the vertical concatenation of the two diagrams.

Definition

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, \text : \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 \circ F_1 \ = \ F_0 \circ \text

and

\text \circ F_1 \ = \ F_0 \circ \text

. Thus we get the category

\mathbf

of monoidal signatures and their morphisms. There is a forgetful functor

U : \mathbf \to \mathbf

which sends a monoidal category to its underlying signature and a

monoidal functor In category theory, monoidal functors are functors between monoidal categories which preserve the monoidal structure. More specifically, a monoidal functor between two monoidal categories consists of a functor between the categories, along with two ...

to its underlying morphism of signatures, i.e. it forgets the identity, composition and tensor. The free functor

C_- : \mathbf \to \mathbf

, 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

topological graph In mathematics, a topological graph is a representation of a graph in the plane, where the ''vertices'' of the graph are represented by distinct points and the ''edges'' by Jordan arcs (connected pieces of ''Jordan curves'') joining the corres ...

, also called a one-dimensional cell complex, is a tuple

(\Gamma, \Gamma_0, \Gamma_1)

of a Hausdorff space

\Gamma

, a

closed Closed may refer to: Mathematics * Closure (mathematics), a set, along with operations, for which applying those operations on members always results in a member of the set * Closed set, a set which contains all its limit points * Closed interval, ...

discrete subset ] In mathematics, a point ''x'' is called an isolated point of a subset ''S'' (in a topological space ''X'') if ''x'' is an element of ''S'' and there exists a neighborhood of ''x'' which does not contain any other points of ''S''. This is equiv ...

\Gamma_0 \subseteq \Gamma

of nodes and a set of Connected component (topology), 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

with

a < b

is a finite topological graph embedded in

\mathbb \times

, b The comma is a punctuation mark that appears in several variants in different languages. It has the same shape as an apostrophe or single closing quotation mark () in many typefaces, but it differs from them in being placed on the baseline o ...

such that every point

x \in \Gamma \ \cap \ \mathbb \times  \

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(\Gamma), \text(\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 \ - \ \ \times \mathbb

are called inner nodes. A plane graph is progressive, also called recumbent, when the vertical projection

e \to

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(f), \text(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 - \ \times \mathbb \to

is injective, i.e. no two inner nodes are at the same height. In that case, one can define a list

\text(\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 - \ \times \mathbb \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

, 1 The comma is a punctuation mark that appears in several variants in different languages. It has the same shape as an apostrophe or single closing quotation mark () in many typefaces, but it differs from them in being placed on the baseline (t ...

\to

\times \mathbb such that * the image of

h(-, t)

defines a plane graph for all

t \in

, * for all

x \in \Gamma_0

, if

h(x, t)

is an inner node for some

t

it is inner for all

t \in

. A deformation is progressive (generic, labeled) if

h(-, t)

is progressive (generic, labeled) for all

t \in

. 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(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 Category theory is a general theory of mathematical structures and their relations that was introduced by Samuel Eilenberg and Saunders Mac Lane in the middle of the 20th century in their foundational work on algebraic topology. Nowadays, cate ...

and low-dimensional topology, a combinatorial definition is necessary to formalise string diagrams in

computer algebra systems A computer algebra system (CAS) or symbolic algebra system (SAS) is any mathematical software with the ability to manipulate mathematical expressions in a way similar to the traditional manual computations of mathematicians and scientists. The de ...

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, \text : L(\Sigma) \to \Sigma_0^\star

defined in the obvious way. This forms a

directed multigraph In mathematics, and more specifically in graph theory, a multigraph is a graph which is permitted to have multiple edges (also called ''parallel edges''), that is, edges that have the same end nodes. Thus two vertices may be connected by mor ...

, 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(d) \in \Sigma_0^\star

as starting point * a length

\text(d) = n \geq 0

, * a list of

\text(d) = d_1 \dots d_n \in L(\Sigma)

such that

\text(d_1) = \text(d)

and

\text(d_i) = \text(d_)

for all

i < n

. 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(x)

with

\text(\text(x)) = 0

and

\text(\text(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(d') \ \circ \ \text(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(d) \otimes d' \ \circ \ d \otimes \text(d')

. Two diagrams are equal (up to the axioms of monoidal categories) whenever they are in the same equivalence class of the

congruence relation In abstract algebra, a congruence relation (or simply congruence) is an equivalence relation on an algebraic structure (such as a group, ring, or vector space) that is compatible with the structure in the sense that algebraic operations done wi ...

generated by the interchanger:

d \otimes \text(d') \ \circ \ \text(d) \otimes d' \quad = \quad \text(d) \otimes d' \ \circ \ d \otimes \text(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 In computer science, the time complexity is the computational complexity that describes the amount of computer time it takes to run an algorithm. Time complexity is commonly estimated by counting the number of elementary operations performed by ...

. 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 In mathematics, the Eckmann–Hilton argument (or Eckmann–Hilton principle or Eckmann–Hilton theorem) is an argument about two unital magma structures on a Set (mathematics), set where one is a homomorphism for the other. Given this, the stru ...

does not apply.

Extension to 2-categories

The idea is to represent structures of dimension ''d'' by structures of dimension ''2-d'', using Poincaré duality. Thus, * an object is represented by a portion of plane, * a 1-cell

f:A\to B

is represented by a vertical segment—called a ''string''—separating the plane in two (the right part corresponding to ''A'' and the left one to ''B''), * a 2-cell

\alpha:f\Rightarrow g:A\to B

is represented by an intersection of strings (the strings corresponding to ''f'' above the link, the strings corresponding to ''g'' below the link). The parallel composition of 2-cells corresponds to the horizontal juxtaposition of diagrams and the sequential composition to the vertical juxtaposition of diagrams. A monoidal category is equivalent to a 2-category with a single 0-cell. Intuitively, going from monoidal categories to 2-categories amounts to adding colours to the background of string diagrams.

Examples

The snake equation

Consider an

adjunction In mathematics, the term ''adjoint'' applies in several situations. Several of these share a similar formalism: if ''A'' is adjoint to ''B'', then there is typically some formula of the type :(''Ax'', ''y'') = (''x'', ''By''). Specifically, adjoin ...

(F,G,\eta,\varepsilon)

between two categories

\mathcal

and

\mathcal

where

F: \mathcal \leftarrow \mathcal

is left adjoint of

G : \mathcal \rightarrow \mathcal

and the natural transformations

\eta: I \rightarrow GF

and

\varepsilon:FG\rightarrow I

are respectively the unit and the counit. The string diagrams corresponding to these natural transformations are: The string corresponding to the identity functor is drawn as a dotted line and can be omitted. The definition of an adjunction requires the following equalities: :

\begin
(\varepsilon F) \circ F(\eta) &= 1_F\\
G(\varepsilon)\circ (\eta G) &= 1_G
\end

The first one is depicted as A monoidal category where every object has a left and right adjoint is called a rigid category. String diagrams for rigid categories can be defined as non-progressive plane graphs, i.e. the edges can bend backward. In the context of categorical quantum mechanics, this is known as the snake equation. The category of

Hilbert space In mathematics, Hilbert spaces (named after David Hilbert) allow generalizing the methods of linear algebra and calculus from (finite-dimensional) Euclidean vector spaces to spaces that may be infinite-dimensional. Hilbert spaces arise natural ...

s is rigid, this fact underlies the proof of correctness for the quantum teleportation protocol. The unit and counit of the adjunction are an abstraction of the

Bell state The Bell states or EPR pairs are specific quantum states of two qubits that represent the simplest (and maximal) examples of quantum entanglement; conceptually, they fall under the study of quantum information science. The Bell states are a fo ...

and the

Bell measurement The Bell states or EPR pairs are specific quantum states of two qubits that represent the simplest (and maximal) examples of quantum entanglement; conceptually, they fall under the study of quantum information science. The Bell states are a form ...

respectively. If Alice and Bob share two qubits Y and Z in an entangled state and Alice performs a ( post-selected) entangled measurement between Y and another qubit X, then this qubit X will be teleported from Alice to Bob: quantum teleportation is an identity morphism.The same equation appears in the definition of pregroup grammars where it captures the notion of information flow in natural language semantics. This observation has led to the development of the DisCoCat framework and

quantum natural language processing Quantum natural language processing (QNLP) is the application of quantum computing to natural language processing (NLP). It computes word embeddings as parameterised quantum circuits that can solve NLP tasks faster than any classical computer. It ...

Hierarchy of graphical languages

Many extensions of string diagrams have been introduced to represent arrows in monoidal categories with extra structure, forming a hierarchy of graphical languages which is classified in Selinger's ''Survey of graphical languages for monoidal categories.'' * Braided monoidal categories with 3-dimensional diagrams, a generalisation of braid groups. * Symmetric monoidal categories with 4-dimensional diagrams where edges can cross, a generalisation of the symmetric group. * Ribbon categories with 3-dimensional diagrams where the edges are undirected, a generalisation of knot diagrams. * Compact closed categories with 4-dimensional diagrams where the edges are undirected, a generalisation of Penrose graphical notation. *

Dagger categories In category theory, a branch of mathematics, a dagger category (also called involutive category or category with involution) is a category equipped with a certain structure called ''dagger'' or ''involution''. The name dagger category was coined b ...

where every diagram has a horizontal reflection.

List of applications

String diagrams have been used to formalise the following objects of study. * Concurrency theory *

Artificial neural networks Artificial neural networks (ANNs), usually simply called neural networks (NNs) or neural nets, are computing systems inspired by the biological neural networks that constitute animal brains. An ANN is based on a collection of connected unit ...

Game theory Game theory is the study of mathematical models of strategic interactions among rational agents. Myerson, Roger B. (1991). ''Game Theory: Analysis of Conflict,'' Harvard University Press, p.&nbs1 Chapter-preview links, ppvii–xi It has appli ...

* Bayesian probability * Consciousness * Markov kernels * Signal-flow graphs * Conjunctive queries * Bidirectional transformations * Categorical quantum mechanics * Quantum circuits, measurement-based quantum computing and

quantum error correction Quantum error correction (QEC) is used in quantum computing to protect quantum information from errors due to decoherence and other quantum noise. Quantum error correction is theorised as essential to achieve fault tolerant quantum computing that ...

, see

ZX-calculus The ZX-calculus is a rigorous graphical language for reasoning about linear maps between qubits, which are represented as string diagrams called ''ZX-diagrams''. A ZX-diagram consists of a set of generators called ''spiders'' that represent speci ...

Natural language processing Natural language processing (NLP) is an interdisciplinary subfield of linguistics, computer science, and artificial intelligence concerned with the interactions between computers and human language, in particular how to program computers to pro ...

, see DisCoCat *

Quantum natural language processing Quantum natural language processing (QNLP) is the application of quantum computing to natural language processing (NLP). It computes word embeddings as parameterised quantum circuits that can solve NLP tasks faster than any classical computer. It ...

History

Intuition

Definition

Algebraic

Geometric

Combinatorial

Extension to 2-categories

Examples

The snake equation

Hierarchy of graphical languages

List of applications

See also

References

External links

External links