Document Open Access Logo

Diagrammatic Polyhedral Algebra

Authors Filippo Bonchi , Alessandro Di Giorgio , Paweł Sobociński

PDF
Thumbnail PDF

File

LIPIcs.FSTTCS.2021.40.pdf
  • Filesize: 0.82 MB
  • 18 pages

Document Identifiers

Author Details

Filippo Bonchi
  • University of Pisa, Italy
Alessandro Di Giorgio
  • University of Pisa, Italy
Paweł Sobociński
  • Tallinn University of Technology, Estonia

Funding

  • Bonchi, Filippo: Supported by the Ministero dell’Università e della Ricerca of Italy under Grant No. 201784YSZ5, PRIN2017 – ASPRA (Analysis of Program Analyses).
  • Di Giorgio, Alessandro: Supported by the Ministero dell’Università e della Ricerca of Italy under Grant No. 201784YSZ5, PRIN2017 – ASPRA (Analysis of Program Analyses).
  • Sobociński, Paweł: Supported by the ESF funded Estonian IT Academy research measure (project 2014-2020.4.05.19-0001) and the Estonian Research Council grant PRG1210.

Acknowledgements

The authors have benefited, at the early stage of this work, of enlightening comments and exciting discussions with Guillaume Boisseau. In particular, Guillaume proposed several simplifications to the axiomatisations, showed us the first proof of the generalised spider and the one for its polar.

Cite AsGet BibTex

Filippo Bonchi, Alessandro Di Giorgio, and Paweł Sobociński. Diagrammatic Polyhedral Algebra. In 41st IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 213, pp. 40:1-40:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
https://doi.org/10.4230/LIPIcs.FSTTCS.2021.40

Abstract

We extend the theory of Interacting Hopf algebras with an order primitive, and give a sound and complete axiomatisation of the prop of polyhedral cones. Next, we axiomatise an affine extension and prove soundness and completeness for the prop of polyhedra.

Subject Classification

ACM Subject Classification
  • Theory of computation → Categorical semantics
  • Theory of computation → Concurrency
Keywords
  • String diagrams
  • Polyhedral cones
  • Polyhedra

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

References

  1. Ravindra K. Ahuja, Thomas L. Magnanti, and James B. Orlin. Network Flows: Theory, Algorithms, and Applications. Prentice-Hall, Inc., USA, 1993. Google Scholar
  2. John Baez and Jason Erbele. Categories in control. Theory and Applications of Categories, 30:836-881, 2015. URL: http://arxiv.org/abs/1405.6881.
  3. John C. Baez. Network theory, 2014. URL: http://math.ucr.edu/home/baez/networks/.
  4. John C Baez and Brendan Fong. A compositional framework for passive linear networks. arXiv preprint, 2015. URL: http://arxiv.org/abs/1504.05625.
  5. Filippo Bonchi, Alessandro Di Giorgio, and Pawel Sobocinski. Diagrammatic polyhedral algebra, 2021. URL: http://arxiv.org/abs/2105.10946.
  6. Filippo Bonchi, Joshua Holland, Dusko Pavlovic, and Paweł Sobociński. Refinement for signal flow graphs. In 28th International Conference on Concurrency Theory, CONCUR 2017, September 5-8, 2017, Berlin, Germany, pages 24:1-24:16, 2017. URL: https://doi.org/10.4230/LIPIcs.CONCUR.2017.24.
  7. Filippo Bonchi, Joshua Holland, Robin Piedeleu, Pawel Sobocinski, and Fabio Zanasi. Diagrammatic algebra: from linear to concurrent systems. Proc. ACM Program. Lang., 3(POPL):25:1-25:28, 2019. URL: https://doi.org/10.1145/3290338.
  8. Filippo Bonchi, Joshua Holland, Robin Piedeleu, Paweł Sobociński, and Fabio Zanasi. Diagrammatic algebra: from linear to concurrent systems. Proceedings of the 46th ACM SIGPLAN Symposium on Principles of Programming Languages (POPL), 3:1-28, 2019. Google Scholar
  9. Filippo Bonchi, Robin Piedeleu, Paweł Sobociński, and Fabio Zanasi. Graphical affine algebra. In Proceedings of the 34th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS), pages 1-12, 2019. Google Scholar
  10. Filippo Bonchi, Jens Seeber, and Pawel Sobocinski. Graphical Conjunctive Queries. In Dan Ghica and Achim Jung, editors, 27th EACSL Annual Conference on Computer Science Logic (CSL 2018), volume 119 of Leibniz International Proceedings in Informatics (LIPIcs), pages 13:1-13:23, Dagstuhl, Germany, 2018. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik. URL: https://doi.org/10.4230/LIPIcs.CSL.2018.13.
  11. Filippo Bonchi, Paweł Sobociński, and Fabio Zanasi. A categorical semantics of signal flow graphs. In Proceedings of the 25th International Conference on Concurrency Theory (CONCUR), pages 435-450. Springer, 2014. Google Scholar
  12. Filippo Bonchi, Pawel Sobocinski, and Fabio Zanasi. Full abstraction for signal flow graphs. In Proceedings of the 42nd Annual ACM SIGPLAN Symposium on Principles of Programming Languages (POPL), pages 515-526, 2015. Google Scholar
  13. Filippo Bonchi, Pawel Sobocinski, and Fabio Zanasi. The calculus of signal flow diagrams I: linear relations on streams. Information and Computation, 252:2-29, 2017. Google Scholar
  14. Bob Coecke and Ross Duncan. Interacting quantum observables: categorical algebra and diagrammatics. New Journal of Physics, 13(4):043016, 2011. Google Scholar
  15. Bob Coecke, Ross Duncan, Aleks Kissinger, and Quanlong Wang. Strong complementarity and non-locality in categorical quantum mechanics. In LiCS 2012, pages 245-254, 2012. Google Scholar
  16. Bob Coecke and Aleks Kissinger. Picturing Quantum Processes - A first course in Quantum Theory and Diagrammatic Reasoning. Cambridge University Press, 2017. Google Scholar
  17. Patrick Cousot and Radhia Cousot. Abstract interpretation: A unified lattice model for static analysis of programs by construction or approximation of fixpoints. In Robert M. Graham, Michael A. Harrison, and Ravi Sethi, editors, Conference Record of the Fourth ACM Symposium on Principles of Programming Languages, Los Angeles, California, USA, January 1977, pages 238-252. ACM, 1977. URL: https://doi.org/10.1145/512950.512973.
  18. René David and Hassane Alla. Discrete, Continuous, and Hybrid Petri Nets. Springer, Berlin, 2 edition, 2010. URL: https://doi.org/10.1007/978-3-642-10669-9.
  19. Brendan Fong and David Spivak. String diagrams for regular logic (extended abstract). In John Baez and Bob Coecke, editors, Applied Category Theory 2019, volume 323 of Electronic Proceedings in Theoretical Computer Science, pages 196-229. Open Publishing Association, September 2020. URL: https://doi.org/10.4204/eptcs.323.14.
  20. Dan R Ghica and Achim Jung. Categorical semantics of digital circuits. In Proceedings of the 16th Conference on Formal Methods in Computer-Aided Design (FMCAD), pages 41-48, 2016. Google Scholar
  21. Nathan Haydon and Paweł Sobociński. Compositional diagrammatic first-order logic. In 11th International Conference on the Theory and Application of Diagrams (DIAGRAMS 2020), 2020. Google Scholar
  22. Naohiko Hoshino, Koko Muroya, and Ichiro Hasuo. Memoryful geometry of interaction: from coalgebraic components to algebraic effects. In Proceedings of the Joint Meeting of the Twenty-Third EACSL Annual Conference on Computer Science Logic (CSL) and the Twenty-Ninth Annual ACM/IEEE Symposium on Logic in Computer Science (LICS), page 52. ACM, 2014. Google Scholar
  23. Bart Jacobs and Fabio Zanasi. The logical essentials of bayesian reasoning. CoRR, abs/1804.01193, 2018. URL: http://arxiv.org/abs/1804.01193.
  24. Franciscus Rebro John C. Baez, Brandon Coya. Props in network theory. CoRR, abs/1707.08321, 2017. URL: http://arxiv.org/abs/1707.08321.
  25. P Katis, N Sabadini, and RFC Walters. Bicategories of processes. Journal of Pure and Applied Algebra, 115(2):141-178, 1997. Google Scholar
  26. Stephen Lack. Composing PROPs. Theory and Application of Categories, 13(9):147-163, 2004. Google Scholar
  27. Yves Lafont. Towards an algebraic theory of Boolean circuits. Journal of Pure and Applied Algebra, 184(2-3):257-310, 2003. Google Scholar
  28. Saunders Mac Lane. Categorical algebra. Bulletin of the American Mathematical Society, 71:40-106, 1965. Google Scholar
  29. Samuel J Mason. Feedback Theory: I. Some Properties of Signal Flow Graphs. MIT Research Laboratory of Electronics, 1953. Google Scholar
  30. Robin Piedeleu and Fabio Zanasi. A string diagrammatic axiomatisation of finite-state automata. In FoSSaCS 2021, 2021. Google Scholar
  31. Peter Selinger. A survey of graphical languages for monoidal categories. Springer Lecture Notes in Physics, 13(813):289-355, 2011. Google Scholar
  32. Fabio Zanasi. Interacting Hopf Algebras: the theory of linear systems. PhD thesis, Ecole Normale Supérieure de Lyon, 2015. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact