String diagrams are a formal graphical language for representing
morphisms
In mathematics, particularly in category theory, a morphism is a structure-preserving map from one mathematical structure to another one of the same type. The notion of morphism recurs in much of contemporary mathematics. In set theory, morphisms ...
in
monoidal categories
In mathematics, a monoidal category (or tensor category) is a category \mathbf C equipped with a bifunctor
:\otimes : \mathbf \times \mathbf \to \mathbf
that is associative up to a natural isomorphism, and an object ''I'' that is both a left and r ...
, 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. When interpreted in the monoidal category of
vector spaces
In mathematics and physics, a vector space (also called a linear space) is a set whose elements, often called ''vectors'', may be added together and multiplied ("scaled") by numbers called ''scalars''. Scalars are often real numbers, but can ...
and
linear map
In mathematics, and more specifically in linear algebra, a linear map (also called a linear mapping, linear transformation, vector space homomorphism, or in some contexts linear function) is a mapping V \to W between two vector spaces that pr ...
s with the
tensor product
In mathematics, the tensor product V \otimes W of two vector spaces and (over the same field) is a vector space to which is associated a bilinear map V\times W \to V\otimes W that maps a pair (v,w),\ v\in V, w\in W to an element of V \otime ...
, string diagrams are called
tensor network
Tensor networks or tensor network states are a class of variational wave functions used in the study of many-body quantum systems. Tensor networks extend one-dimensional matrix product states to higher dimensions while preserving some of their use ...
s or
Penrose graphical notation
In mathematics and physics, Penrose graphical notation or tensor diagram notation is a (usually handwritten) visual depiction of multilinear functions or tensors proposed by Roger Penrose in 1971. A diagram in the notation consists of several sha ...
. This has led to the development of
categorical quantum mechanics
Categorical quantum mechanics is the study of quantum foundations and quantum information using paradigms from mathematics and computer science, notably monoidal category theory. The primitive objects of study are physical processes, and the diffe ...
where the axioms of quantum theory are expressed in the language of monoidal categories.
History
Günter Hotz gave the first mathematical definition of string diagrams in order to formalise
electronic circuits, but the article remained confidential because of the absence of an English translation. The invention of string diagrams is usually credited to
Roger Penrose with
Feynman diagram
In theoretical physics, a Feynman diagram is a pictorial representation of the mathematical expressions describing the behavior and interaction of subatomic particles. The scheme is named after American physicist Richard Feynman, who introduc ...
s also described as a precursor. They were later characterised as the arrows of
free monoidal categories in a seminal article by
André Joyal
André Joyal (; born 1943) is a professor of mathematics at the Université du Québec à Montréal who works on category theory. He was a member of the School of Mathematics at the Institute for Advanced Study in 2013, where he was invited to jo ...
and
Ross Street. While the diagrams in these first articles were hand-drawn, the advent of typesetting software such as
LaTeX
Latex is an emulsion (stable dispersion) of polymer microparticles in water. Latexes are found in nature, but synthetic latexes are common as well.
In nature, latex is found as a milky fluid found in 10% of all flowering plants (angiosperms ...
and
PGF/TikZ
PGF/Ti''k''Z is a pair of languages for producing vector graphics (e.g., technical illustrations and drawings) from a geometric/algebraic description, with standard features including the drawing of points, lines, arrows, paths, circles, ellipse ...
made the publication of string diagrams more wide-spread.
The
existential graph
An existential graph is a type of diagrammatic or visual notation for logical expressions, proposed by Charles Sanders Peirce, who wrote on graphical logic as early as 1882,Peirce, C. S., " n Junctures and Fractures in Logic (editors' title for ...
s and
diagrammatic reasoning of
Charles Sanders Peirce
Charles Sanders Peirce ( ; September 10, 1839 – April 19, 1914) was an American philosopher, logician, mathematician and scientist who is sometimes known as "the father of pragmatism".
Educated as a chemist and employed as a scientist for t ...
are arguably the oldest form of string diagrams, they are interpreted in the monoidal category of
finite sets
In mathematics, particularly set theory, a finite set is a set that has a finite number of elements. Informally, a finite set is a set which one could in principle count and finish counting. For example,
:\
is a finite set with five elements. Th ...
and
relations with the
Cartesian product. The lines of identity of Peirce's existential graphs can be axiomatised as a
Frobenius algebra
In mathematics, especially in the fields of representation theory and module theory, a Frobenius algebra is a finite-dimensional unital associative algebra with a special kind of bilinear form which gives the algebras particularly nice duality th ...
, the cuts are unary operators on homsets that axiomatise
logical negation. This makes string diagrams a
sound
In physics, sound is a vibration that propagates as an acoustic wave, through a transmission medium such as a gas, liquid or solid.
In human physiology and psychology, sound is the ''reception'' of such waves and their ''perception'' b ...
and
complete two-dimensional
deduction system
A formal system is an abstract structure used for inferring theorems from axioms according to a set of rules. These rules, which are used for carrying out the inference of theorems from axioms, are the logical calculus of the formal system.
A form ...
for
first-order logic
First-order logic—also known as predicate logic, quantificational logic, and first-order predicate calculus—is a collection of formal systems used in mathematics, philosophy, linguistics, and computer science. First-order logic uses quantifie ...
, invented independently from the one-dimensional syntax of
Gottlob Frege
Friedrich Ludwig Gottlob Frege (; ; 8 November 1848 – 26 July 1925) was a German philosopher, logician, and mathematician. He was a mathematics professor at the University of Jena, and is understood by many to be the father of analytic ph ...
's
Begriffsschrift
''Begriffsschrift'' (German for, roughly, "concept-script") is a book on logic by Gottlob Frege, published in 1879, and the formal system set out in that book.
''Begriffsschrift'' is usually translated as ''concept writing'' or ''concept notatio ...
.
Intuition
String diagrams are made of boxes
, which represent
processes, with a list of wires
coming in at the top and
at the bottom, which represent the input and output
systems being processed by the box
. Starting from a collection of wires and boxes, called a signature, one may generate the set of all string diagrams by induction:
* each box
is a string diagram,
* for each list of wires
, the
identity
Identity may refer to:
* Identity document
* Identity (philosophy)
* Identity (social science)
* Identity (mathematics)
Arts and entertainment Film and television
* ''Identity'' (1987 film), an Iranian film
* ''Identity'' (2003 film), ...
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
and
, their
tensor
In mathematics, a tensor is an algebraic object that describes a multilinear relationship between sets of algebraic objects related to a vector space. Tensors may map between different objects such as vectors, scalars, and even other tensor ...
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
and
, their
composition
Composition or Compositions may refer to:
Arts and literature
*Composition (dance), practice and teaching of choreography
*Composition (language), in literature and rhetoric, producing a work in spoken tradition and written discourse, to include v ...
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
In mathematical logic and computer science, the Kleene star (or Kleene operator or Kleene closure) is a unary operation, either on sets of strings or on sets of symbols or characters. In mathematics,
it is more commonly known as the free monoid ...
denote the
free monoid In abstract algebra, the free monoid on a set is the monoid whose elements are all the finite sequences (or strings) of zero or more elements from that set, with string concatenation as the monoid operation and with the unique sequence of zero ele ...
, i.e. the set of lists with elements in a set
.
A monoidal signature
is given by:
* a set
of generating objects, the lists of generating objects in
are also called types,
* a set
of generating arrows, also called boxes,
* a pair of functions
which assign a domain and codomain to each box, i.e. the input and output types.
A morphism of monoidal signature
is a pair of functions
and
which is compatible with the domain and codomain, i.e. such that
and
. Thus we get the category
of monoidal signatures and their morphisms.
There is a
forgetful functor In mathematics, in the area of category theory, a forgetful functor (also known as a stripping functor) 'forgets' or drops some or all of the input's structure or properties 'before' mapping to the output. For an algebraic structure of a given sign ...
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
In mathematics, the idea of a free object is one of the basic concepts of abstract algebra. Informally, a free object over a set ''A'' can be thought of as being a "generic" algebraic structure over ''A'': the only equations that hold between elem ...
, i.e. the
left adjoint
In mathematics, specifically category theory, adjunction is a relationship that two functors may exhibit, intuitively corresponding to a weak form of equivalence between two related categories. Two functors that stand in this relationship are kno ...
to the forgetful functor, sends a monoidal signature
to the
free monoidal category it generates.
String diagrams (with generators from
) are arrows in the free monoidal category
. The interpretation in a monoidal category
is a defined by a monoidal functor
, which by freeness is uniquely determined by a morphism of monoidal signatures
. 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
A CW complex (also called cellular complex or cell complex) is a kind of a topological space that is particularly important in algebraic topology. It was introduced by J. H. C. Whitehead (open access) to meet the needs of homotopy theory. This clas ...
, is a tuple
of a
Hausdorff space
In topology and related branches of mathematics, a Hausdorff space ( , ), separated space or T2 space is a topological space where, for any two distinct points, there exist neighbourhoods of each which are disjoint from each other. Of the m ...
, a
closed discrete subset of nodes and a set of
connected components called edges, each homeomorphic to an open interval with boundary in
and such that
.
A
plane graph
In graph theory, a planar graph is a graph that can be embedded in the plane, i.e., it can be drawn on the plane in such a way that its edges intersect only at their endpoints. In other words, it can be drawn in such a way that no edges cros ...
between two real numbers
with
is a finite topological graph embedded in
such that every point
is also a node
and belongs to the closure of exactly one edge in
. Such points are called outer nodes, they define the domain and codomain
of the string diagram, i.e. the list of edges that are connected to the top and bottom boundary. The other nodes
are called inner nodes.
A plane graph is progressive, also called recumbent, when the vertical projection
is injective for every edge
. 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
of each inner node
, given by the list of edges that have source and target.
A plane graph is generic when the vertical projection
is injective, i.e. no two inner nodes are at the same height. In that case, one can define a list
of the inner nodes ordered from top to bottom.
A progressive plane graph is labeled by a monoidal signature
if it comes equipped with a pair of functions
from edges to generating objects and
from inner nodes to generating arrows, in a way compatible with domain and codomain.
A deformation of plane graphs is a
continuous map
In mathematics, a continuous function is a function such that a continuous variation (that is a change without jump) of the argument induces a continuous variation of the value of the function. This means that there are no abrupt changes in valu ...
such that
* the image of
defines a plane graph for all
,
* for all
, if
is an inner node for some
it is inner for all
.
A deformation is progressive (generic, labeled) if
is progressive (generic, labeled) for all
. Deformations induce an equivalence relation with
if and only if there is some
with
and
. String diagrams are equivalence classes of labeled progressive plane graphs. Indeed, one can define:
* the identity diagram
as a set of parallel edges labeled by some type
,
* 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
In mathematics, low-dimensional topology is the branch of topology that studies manifolds, or more generally topological spaces, of four or fewer dimensions. Representative topics are the structure theory of 3-manifolds and 4-manifolds, knot th ...
, a combinatorial definition is necessary to formalise string diagrams in
computer algebra systems and use them to define
computational problems
In theoretical computer science, a computational problem is a problem that may be solved by an algorithm. For example, the problem of factoring
:"Given a positive integer ''n'', find a nontrivial prime factor of ''n''."
is a computational probl ...
. 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
. A layer is defined as a triple
of a type
on the left, a box
in the middle and a type
on the right. Layers have a domain and codomain
defined in the obvious way. This forms a
directed multigraph, also known as a
quiver
A quiver is a container for holding arrows, bolts, ammo, projectiles, darts, or javelins. It can be carried on an archer's body, the bow, or the ground, depending on the type of shooting and the archer's personal preference. Quivers were trad ...
, with the types as vertices and the layers as edges. A string diagram
is encoded as a path in this multigraph, i.e. it is given by:
* a domain
as starting point
* a length
,
* a list of
such that
and
for all
. 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
of a diagram
by a type
is defined as the concatenation to the right of each layer
and symmetrically for the whiskering
on the left. One can then define:
* the identity diagram
with
and
,
* the composition of two diagrams as the concatenation of their list of layers,
* the tensor of two diagrams as the composition of whiskerings
.
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
.
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:
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
In geography, a confluence (also: ''conflux'') occurs where two or more flowing bodies of water join to form a single channel. A confluence can occur in several configurations: at the point where a tributary joins a larger river (main stem); o ...
rewriting system
In mathematics, computer science, and logic, rewriting covers a wide range of methods of replacing subterms of a formula with other terms. Such methods may be achieved by rewriting systems (also known as rewrite systems, rewrite engines, or reduc ...
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
The idea is to represent structures of dimension ''d'' by structures of dimension ''2-d'', using
Poincaré duality
In mathematics, the Poincaré duality theorem, named after Henri Poincaré, is a basic result on the structure of the homology and cohomology groups of manifolds. It states that if ''M'' is an ''n''-dimensional oriented closed manifold (compact ...
. Thus,
* an object is represented by a portion of plane,
* a 1-cell
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
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 between two categories
and
where
is left adjoint of
and the
natural transformation
In category theory, a branch of mathematics, a natural transformation provides a way of transforming one functor into another while respecting the internal structure (i.e., the composition of morphisms) of the categories involved. Hence, a natur ...
s
and
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:
:
The first one is depicted as
A monoidal category where every object has a left and right adjoint is called a
rigid category In category theory, a branch of mathematics, a rigid category is a monoidal category where every object is rigid, that is, has a dual ''X''* (the internal Hom 'X'', 1 and a morphism 1 → ''X'' ⊗ ''X''* satisfying natural conditions. The ...
. 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
Categorical quantum mechanics is the study of quantum foundations and quantum information using paradigms from mathematics and computer science, notably monoidal category theory. The primitive objects of study are physical processes, and the diffe ...
, this is known as the snake equation.
The category of
Hilbert spaces 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 form o ...
and the
Bell measurement respectively. If Alice and Bob share two
qubits
In quantum computing, a qubit () or quantum bit is a basic unit of quantum information—the quantum version of the classic binary bit physically realized with a two-state device. A qubit is a two-state (or two-level) quantum-mechanical system, ...
Y and Z in an
entangled state
Quantum entanglement is the phenomenon that occurs when a group of particles are generated, interact, or share spatial proximity in a way such that the quantum state of each particle of the group cannot be described independently of the state of ...
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 grammar Pregroup grammar (PG) is a grammar formalism intimately related to categorial grammars. Much like categorial grammar (CG), PG is a kind of type logical grammar. Unlike CG, however, PG does not have a distinguished function type. Rather, PG uses in ...
s where it captures the notion of
information flow
In discourse-based grammatical theory, information flow is any tracking of referential information by speakers. Information may be ''new,'' just introduced into the conversation; ''given,'' already active in the speakers' consciousness; or ''old, ...
in
natural language semantics
Semantics (from grc, σημαντικός ''sēmantikós'', "significant") is the study of reference, meaning, or truth. The term can be used to refer to subfields of several distinct disciplines, including philosophy, linguistics and comput ...
. This observation has led to the development of the
DisCoCat
DisCoCat (Categorical Compositional Distributional) is a mathematical framework for natural language processing which uses category theory to unify distributional semantics with the principle of compositionality. The grammatical derivations in a ...
framework and
quantum natural language processing.
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 In mathematics, a ''commutativity constraint'' \gamma on a monoidal category ''\mathcal'' is a choice of isomorphism \gamma_ : A\otimes B \rightarrow B\otimes A for each pair of objects ''A'' and ''B'' which form a "natural family." In particu ...
with 3-dimensional diagrams, a generalisation of
braid group
A braid (also referred to as a plait) is a complex structure or pattern formed by interlacing two or more strands of flexible material such as textile yarns, wire, or hair.
The simplest and most common version is a flat, solid, three-strande ...
s.
*
Symmetric monoidal categories with 4-dimensional diagrams where edges can cross, a generalisation of the
symmetric group
In abstract algebra, the symmetric group defined over any set is the group whose elements are all the bijections from the set to itself, and whose group operation is the composition of functions. In particular, the finite 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
In mathematics and physics, Penrose graphical notation or tensor diagram notation is a (usually handwritten) visual depiction of multilinear functions or tensors proposed by Roger Penrose in 1971. A diagram in the notation consists of several sha ...
.
*
Dagger categories 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
*
Game theory
*
Bayesian probability
Bayesian probability is an interpretation of the concept of probability, in which, instead of frequency or propensity of some phenomenon, probability is interpreted as reasonable expectation representing a state of knowledge or as quantification ...
*
Consciousness
Consciousness, at its simplest, is sentience and awareness of internal and external existence. However, the lack of definitions has led to millennia of analyses, explanations and debates by philosophers, theologians, linguisticians, and scien ...
*
Markov kernels
*
Signal-flow graph
A signal-flow graph or signal-flowgraph (SFG), invented by Claude Shannon, but often called a Mason graph after Samuel Jefferson Mason who coined the term, is a specialized flow graph, a directed graph in which nodes represent system variables, ...
s
*
Conjunctive queries
*
Bidirectional transformation
In computer programming, bidirectional transformations (bx) are programs in which a single piece of code can be run in several ways, such that the same data are sometimes considered as input, and sometimes as output. For example, a bx run in the fo ...
s
*
Categorical quantum mechanics
Categorical quantum mechanics is the study of quantum foundations and quantum information using paradigms from mathematics and computer science, notably monoidal category theory. The primitive objects of study are physical processes, and the diffe ...
*
Quantum circuit
In quantum information theory, a quantum circuit is a model for quantum computation, similar to classical circuits, in which a computation is a sequence of quantum gates, measurements, initializations of qubits to known values, and possibly o ...
s,
measurement-based quantum computing and
quantum error correction, see
ZX-calculus
*
Natural language processing, see
DisCoCat
DisCoCat (Categorical Compositional Distributional) is a mathematical framework for natural language processing which uses category theory to unify distributional semantics with the principle of compositionality. The grammatical derivations in a ...
*
Quantum natural language processing
See also
*
Proof nets, a generalisation of string diagrams used to denote proofs in
linear logic
*
Existential graphs, a precursor of string diagrams used to denote formulae in
first-order logic
First-order logic—also known as predicate logic, quantificational logic, and first-order predicate calculus—is a collection of formal systems used in mathematics, philosophy, linguistics, and computer science. First-order logic uses quantifie ...
*
Penrose graphical notation
In mathematics and physics, Penrose graphical notation or tensor diagram notation is a (usually handwritten) visual depiction of multilinear functions or tensors proposed by Roger Penrose in 1971. A diagram in the notation consists of several sha ...
and
Feynman diagram
In theoretical physics, a Feynman diagram is a pictorial representation of the mathematical expressions describing the behavior and interaction of subatomic particles. The scheme is named after American physicist Richard Feynman, who introduc ...
s, two precursors of string diagrams in physics
*
Tensor network
Tensor networks or tensor network states are a class of variational wave functions used in the study of many-body quantum systems. Tensor networks extend one-dimensional matrix product states to higher dimensions while preserving some of their use ...
s, the interpretation of string diagrams in
vector space
In mathematics and physics, a vector space (also called a linear space) is a set whose elements, often called '' vectors'', may be added together and multiplied ("scaled") by numbers called ''scalars''. Scalars are often real numbers, but can ...
s,
linear map
In mathematics, and more specifically in linear algebra, a linear map (also called a linear mapping, linear transformation, vector space homomorphism, or in some contexts linear function) is a mapping V \to W between two vector spaces that pr ...
s and
tensor product
In mathematics, the tensor product V \otimes W of two vector spaces and (over the same field) is a vector space to which is associated a bilinear map V\times W \to V\otimes W that maps a pair (v,w),\ v\in V, w\in W to an element of V \otime ...
References
External links
*
*
DisCoPy a Python toolkit for computing with string diagrams
External links
*
{{DEFAULTSORT:String Diagram
Higher category theory
Monoidal categories