2021/12/13 by Matt Wilson, Matthew E. Wilson, Wilson, Matt +2 · 3 citations
Computer Science · Mathematics · Physics and Astronomy · #Category Theory (math.CT) #Constraint Satisfaction and Optimization #FOS: Computer and information sciences #FOS: Mathematics #FOS: Physical sciences #Homotopy and Cohomology in Algebraic Topology #Logic in Computer Science (cs.LO) #Quantum Mechanics and Applications #Quantum Physics (quant-ph) #cs.LO #math.CT #quant-ph
paper · pdf · doi:10.48550/arxiv.2112.06818
arxiv created 2021/12/13 · openalex publication_date 2021/12/13 · arxiv updated 2021/12/14 · openalex created_date 2022/05/05 · openalex updated_date 2026/07/28
We introduce a notion of compatibility between constraint encoding and compositional structure. Phrased in the language of category theory, it is given by a "composable constraint encoding". We show that every composable constraint encoding can be used to construct an equivalent notion of a constrained category in which morphisms are supplemented with the constraints they satisfy. We further describe how to express the compatibility of constraints with additional categorical structures of their targets, such as parallel composition, compactness, and time-symmetry. We present a variety of concrete examples. Some are familiar in the study of quantum protocols and quantum foundations, such as signalling and sectorial constraints; others arise by construction from basic categorical notions. We use the language developed to discuss the notion of intersectability of constraints and the simplifications it allows for when present, and to show that any time-symmetric theory of relational constraints admits a faithful notion of intersection.