LIPIcs.CALCO.2017.12.pdf
- Filesize: 0.57 MB
- 16 pages
Document
A Universal Construction for (Co)Relations
Authors
-
Part of:
Volume:
7th Conference on Algebra and Coalgebra in Computer Science (CALCO 2017)
Series: Leibniz International Proceedings in Informatics (LIPIcs)
Conference: Conference on Algebra and Coalgebra in Computer Science (CALCO) - License:
Creative Commons Attribution 3.0 Unported license
- Publication Date: 2017-11-17
Cite AsGet BibTex
Brendan Fong and Fabio Zanasi. A Universal Construction for (Co)Relations. In 7th Conference on Algebra and Coalgebra in Computer Science (CALCO 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 72, pp. 12:1-12:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
https://doi.org/10.4230/LIPIcs.CALCO.2017.12
https://doi.org/10.4230/LIPIcs.CALCO.2017.12
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 and are relevant for program semantics, quantum computation and control theory.
Keywords
- corelation
- prop
- string diagram
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads
References
- John C. Baez and Jason Erbele. Categories in control. Theory Appl. Categ., 30:836-881, 2015. URL: http://www.tac.mta.ca/tac/volumes/30/24/30-24abs.html.
- John C. Baez and Brendan Fong. A compositional framework for passive linear circuits. Preprint, 2015. URL: https://arxiv.org/abs/1504.05625.
- Filippo Bonchi, Paweł Sobociński, and Fabio Zanasi. A categorical semantics of signal flow graphs. In CONCUR 2014, volume 8704 of LNCS, pages 435-450. Springer, 2014. URL: http://dx.doi.org/10.1007/978-3-662-44584-6_30.
- Filippo Bonchi, Paweł Sobociński, and Fabio Zanasi. Interacting bialgebras are Frobenius. In FoSSaCS 2014, volume 8412 of LNCS, pages 351-365. Springer, 2014. URL: http://dx.doi.org/10.1007/978-3-642-54830-7_23.
- Filippo Bonchi, Paweł Sobociński, and Fabio Zanasi. Full abstraction for signal flow graphs. In POPL 2015, pages 515-526, 2015. URL: http://dx.doi.org/10.1145/2676726.2676993.
- Filippo Bonchi, Paweł Sobociński, and Fabio Zanasi. The calculus of signal flow diagrams I: linear relations on streams. Inf. Comput., 252:2-29, 2017. URL: http://dx.doi.org/10.1016/j.ic.2016.03.002.
- Filippo Bonchi, Paweł Sobociński, and Fabio Zanasi. Interacting Hopf algebras. Journal of Pure and Applied Algebra, 221(1):144-184, 2017. URL: http://dx.doi.org/10.1016/j.jpaa.2016.06.002.
- Bob Coecke and Ross Duncan. Interacting quantum observables: categorical algebra and diagrammatics. New Journal of Physics, 13(4):043016, 2011. URL: http://dx.doi.org/10.1088/1367-2630/13/4/043016.
- Brandon Coya and Brendan Fong. Corelations are the prop for extraspecial commutative Frobenius monoids. Theory Appl. Categ., 32(11):380-395, 2017. URL: http://www.tac.mta.ca/tac/volumes/32/11/32-11abs.html.
- Brendan Fong. The Algebra of Open and Interconnected Systems. PhD thesis, University of Oxford, 2016. URL: https://arxiv.org/abs/1609.05382.
- Brendan Fong. Decorated corelations. Preprint, 2017. URL: https://arxiv.org/abs/1703.09888.
- Brendan Fong, Paolo Rapisarda, and Paweł Sobociński. A categorical approach to open and interconnected dynamical systems. In LICS 2016, pages 495-504, 2016. URL: http://dx.doi.org/10.1145/2933575.2934556.
- Ichiro Hasuo and Naohiko Hoshino. Semantics of higher-order quantum computation via geometry of interaction. In LICS 2011, pages 237-246, 2011. URL: http://dx.doi.org/10.1109/LICS.2011.26.
-
Chris Heunen and Jamie Vicary. Lectures on categorical quantum mechanics, 2012.
- Bart Jacobs and Jorik Mandemaker. Coreflections in algebraic quantum logic. Foundations of Physics, 42(7):932-958, 2012. URL: http://dx.doi.org/10.1007/s10701-012-9654-8.
- Stephen Lack. Composing PROPs. Theory Appl. Categ., 13(9):147-163, 2004. URL: http://www.tac.mta.ca/tac/volumes/13/9/13-09abs.html.
- Saunders Mac Lane. Categorical algebra. Bulletin of the American Mathematical Society, 71:40-106, 1965. URL: http://dx.doi.org/10.1090/S0002-9904-1965-11234-4.
- Dan Marsden and Fabrizio Genovese. Custom hypergraph categories via generalized relations. Preprint, 2017. URL: https://arxiv.org/abs/1703.01204.
- Jeanne Meisen. On bicategories of relations and pullback spans. Communications in Algebra, 1(5):377-401, 1974. URL: http://dx.doi.org/10.1080/00927877408548625.
- Robert Rosebrugh and R.J. Wood. Distributive laws and factorization. Journal of Pure and Applied Algebra, 175(1-3):327 - 353, 2002. URL: http://dx.doi.org/10.1016/S0022-4049(02)00140-8.
- Dana Scott. Data types as lattices. SIAM Journal on Computing, 5(3):522-587, 1976. URL: http://dx.doi.org/10.1137/0205037.
- Peter Selinger. A survey of graphical languages for monoidal categories. In New Structures for Physics, pages 289-355. Springer, 2011. URL: http://dx.doi.org/10.1007/978-3-642-12821-9_4.
-
Fabio Zanasi. Interacting Hopf Algebras: the theory of linear systems. PhD thesis, Ecole Normale Supérieure de Lyon, 2015.
- Fabio Zanasi. The algebra of partial equivalence relations. Electr. Notes Theor. Comput. Sci., 325:313-333, 2016. URL: http://dx.doi.org/10.1016/j.entcs.2016.09.046.