String diagrams are a formal graphical language for representing morphisms in monoidal categories, or more generally 2-cells in 2-categories.
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.
Günter Hotz gave the first mathematical definition of string diagrams in order to formalise electronic circuits.
[3] They were later characterised as the arrows of free monoidal categories in a seminal article by André Joyal and Ross Street.
[5] 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 with the Cartesian product.
This makes string diagrams a sound and complete two-dimensional deduction system for first-order logic,[7] invented independently from the one-dimensional syntax of Gottlob Frege's Begriffsschrift.
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: Let the Kleene star
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.
, i.e. the left adjoint to the forgetful functor, sends a monoidal signature
A topological graph, also called a one-dimensional cell complex, is a tuple
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.
A plane graph is progressive, also called recumbent, when the vertical projection
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.
String diagrams are equivalence classes of labeled progressive plane graphs.
Indeed, one can define: 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.
This forms a directed multigraph, also known as a quiver, with the types as vertices and the layers as edges.
One can then define: 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.
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:
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.
Intuitively, going from monoidal categories to 2-categories amounts to adding colours to the background of string diagrams.
String diagrams for rigid categories can be defined as non-progressive plane graphs, i.e. the edges can bend backward.
The category of Hilbert spaces is rigid, this fact underlies the proof of correctness for the quantum teleportation protocol.
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.
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.