A Universal Construction for (Co)Relations

Abstract

Calculi of string diagrams are increasingly used to present the syntax and algebraic structure of various families of circuits, including signal flow graphs, electrical circuits and quantum processes. In many such approaches, the semantic interpretation for diagrams is given in terms of relations or corelations (generalised equivalence relations) of some kind. In this paper we show how semantic categories of both relations and corelations can be characterised as colimits of simpler categories. This modular perspective is important as it simplifies the task of giving a complete axiomatisation for semantic equivalence of string diagrams. Moreover, our general result unifies various theorems that are independently found in literature, including the cases of linear corelations (relevant for the semantics of electrical circuits), of partial equivalence relations and of linear subspaces (semantics of signal flow graphs and of the phase-free ZX calculus).

arXiv comment15 pages + 4 page appendix, CALCO 2017

References in corpus (7)

• Physics, Topology, Logic and Computation: A Rosetta Stone
• Compact Closed Bicategories
• A Prehistory of n-Categorical Physics
• The operad of wiring diagrams: formalizing a graphical language for databases, recursion, and plug-and-play circuits
• Corelations are the prop for extraspecial commutative Frobenius monoids
• Categories in control: applied PROPs
• Calculating Colimits Compositionally

Cited by in corpus (37)

• Training End-to-End Analog Neural Networks with Equilibrium Propagation
• DisCoPy: Monoidal Categories in Python
• Discrete curvature on graphs from the effective resistance
• Effective resistance is more than distance: Laplacians, Simplices and the Schur complement
• Corelations are the prop for extraspecial commutative Frobenius monoids
• Operads for complex system design specification, analysis and synthesis
• Knowledge Representation in Bicategories of Relations
• Structured versus Decorated Cospans
• String Diagrammatic Electrical Circuit Theory
• Compositional Models for Power Systems
• A bicategory of decorated cospans
• A Graphical Calculus for Lagrangian Relations
• Custom Hypergraph Categories via Generalized Relations
• Coarse-Graining Open Markov Processes
• A Compositional Approach to Parity Games
• Open Systems in Classical Mechanics
• Circuits, Bond Graphs, and Signal-Flow Diagrams: A Categorical Perspective
• Categories in control: applied PROPs
• String Diagrams for Regular Logic (Extended Abstract)
• Graphical Regular Logic
• A Finite Axiomatisation of Finite-State Automata Using String Diagrams
• Compositional Deep Learning
• Complete ZX-calculi for the stabiliser fragment in odd prime dimensions
• Fast Automated Reasoning over String Diagrams using Multiway Causal Structure
• Kindergarden quantum mechanics graduates (...or how I learned to stop gluing LEGO together and love the ZX-calculus)
• Networks with complex weights: Green function and power series
• Rewriting Structured Cospans: A Syntax For Open Systems
• An Open Petri Net Implementation of Gene Regulatory Networks
• The Abstract Structure of Quantum Algorithms
• Monoidal Width
• A Compositional Framework for Bond Graphs
• Layering $\partial$-Graphs and Networks
• Regular Calculi I: Graphical Regular Logic
• Rewriting Graphically with Symmetric Traced Monoidal Categories
• Normalizing Resistor Networks
• A recipe for black box functors
• Homotopy composition of cospans