Abstract
Graphical (Linear) Algebra is a family of diagrammatic languages allowing to reason about different kinds of subsets of vector spaces compositionally. It has been used to model various application domains, from signal-flow graphs to Petri nets and electrical circuits. In this paper, we introduce to the family its most expressive member to date: Graphical Piecewise-Linear Algebra, a new language to specify piecewise-linear subsets of vector spaces.
Like the previous members of the family, it comes with a complete axiomatisation, which means it can be used to reason about the corresponding semantic domain purely equationally, forgetting the set-theoretic interpretation. We show completeness using a single axiom on top of Graphical Polyhedral Algebra, and show that this extension is the smallest that can capture a variety of relevant constructs.
Finally, we showcase its use by modelling the behaviour of stateless electronic circuits of ideal elements, a domain that had remained outside the remit of previous diagrammatic languages.
Chapter PDF
Similar content being viewed by others
References
Baez, J.C., Coya, B., Rebro, F.: Props in network theory. Theory and Applications of Categories 33(25), 727–783 (2018)
Baez, J.C., Fong, B.: A compositional framework for passive linear networks. Theory and Applications of Categories 33(38), 1158–1222 (2018)
Boisseau, G., Sobociński, P.: String Diagrammatic Electrical Circuit Theory. arXiv:2106.07763 [cs] (2021), http://arxiv.org/abs/2106.07763
Bonchi, F., Di Giorgio, A., Sobocinski, P.: Diagrammatic Polyhedral Algebra. arXiv:2105.10946 [cs, math] (2021), http://arxiv.org/abs/2105.10946
Bonchi, F., Holland, J., Piedeleu, R., Sobociński, P., Zanasi, F.: Diagrammatic algebra: from linear to concurrent systems. In: Proceedings of the 46th Annual ACM SIGPLAN Symposium on Principles of Programming Languages(POPL) (2019)
Bonchi, F., Piedeleu, R., Sobociński, P., Zanasi, F.: Graphical Affine Algebra. In: 34th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS). pp. 1–12. IEEE, Vancouver, BC, Canada (2019). https://doi.org/10.1109/LICS.2019.8785877
Bonchi, F., Sobociński, P., Zanasi, F.: Deconstructing lawvere with distributive laws. Journal of logical and algebraic methods in programming 95, 128–146 (2018)
Cvitanovic, P., Cvitanović, P.: Group theory. Princeton University Press (2008)
Stephan, P.R., Brayton, R.K.: Physically realizable gate models. In: Proceedings of 1993 IEEE International Conference on Computer Design ICCD’93. pp. 442–445. IEEE (1993)
Theraja, B., Theraja, A.: A textbook of electrical technology : in S.I. system of units. Publication division of Nirja Construction and Development Co., New Delhi (1994)
Willems, J.C.: The behavioral approach to open and interconnected systems. IEEE Control Systems Magazine 27(6), 46–99 (2007)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Open Access This chapter is licensed under the terms of the Creative Commons Attribution 4.0 International License (http://creativecommons.org/licenses/by/4.0/), which permits use, sharing, adaptation, distribution and reproduction in any medium or format, as long as you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons license and indicate if changes were made.
The images or other third party material in this chapter are included in the chapter's Creative Commons license, unless indicated otherwise in a credit line to the material. If material is not included in the chapter's Creative Commons license and your intended use is not permitted by statutory regulation or exceeds the permitted use, you will need to obtain permission directly from the copyright holder.
Copyright information
© 2022 The Author(s)
About this paper
Cite this paper
Boisseau, G., Piedeleu, R. (2022). Graphical Piecewise-Linear Algebra. In: Bouyer, P., Schröder, L. (eds) Foundations of Software Science and Computation Structures. FoSSaCS 2022. Lecture Notes in Computer Science, vol 13242. Springer, Cham. https://doi.org/10.1007/978-3-030-99253-8_6
Download citation
DOI: https://doi.org/10.1007/978-3-030-99253-8_6
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-99252-1
Online ISBN: 978-3-030-99253-8
eBook Packages: Computer ScienceComputer Science (R0)