Abstract
We extend the signal flow calculus—a compositional account of the classical signal flow graph model of computation—to encompass affine behaviour, and furnish it with a novel operational semantics. The increased expressive power allows us to define a canonical notion of contextual equivalence, which we show to coincide with denotational equality. Finally, we characterise the realisable fragment of the calculus: those terms that express the computations of (affine) signal flow graphs.
R. Piedeleu, F. Zanasi—Supported by EPSRC grant EP/R020604/1.
P. Sobociński—Supported by the ESF funded Estonian IT Academy research measure (project 2014-2020.4.05.19-0001)
Chapter PDF
Similar content being viewed by others
References
Abramsky, S., Coecke, B.: A categorical semantics of quantum protocols. In: Proceedings of the 19th Annual IEEE Symposium on Logic in Computer Science (LICS), 2004. pp. 415–425. IEEE (2004)
Baez, J., Erbele, J.: Categories in control. Theory and Applications of Categories 30, 836–881 (2015)
Baez, J.C.: Network theory (2014), http://math.ucr.edu/home/baez/networks/, website (retrieved 15/04/2014)
Basold, H., Bonsangue, M., Hansen, H., Rutten, J.: (Co)Algebraic characterizations of signal flow graphs. In: van Breugel, F., Kashefi, E., Palamidessi, C., Rutten, J. (eds.) Horizons of the Mind. A Tribute to Prakash Panangaden, Lecture Notes in Computer Science, vol. 8464, pp. 124–145. Springer International Publishing (2014)
Bonchi, F., Holland, J., Piedeleu, R., Sobociński, P., Zanasi, F.: Diagrammatic algebra: from linear to concurrent systems. Proceedings of the 46th ACM SIGPLAN Symposium on Principles of Programming Languages (POPL) 3, 1–28 (2019)
Bonchi, F., Piedeleu, R., Sobociński, P., Zanasi, F.: Graphical affine algebra. In: Proceedings of the 34th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS). pp. 1–12 (2019)
Bonchi, F., Piedeleu, R., Sobociński, P., Zanasi, F.: Contextual equivalence for signal flow graphs (2020), https://arxiv.org/abs/2002.08874
Bonchi, F., Sobociński, P., Zanasi, F.: A categorical semantics of signal flow graphs. In: Proceedings of the 25th International Conference on Concurrency Theory (CONCUR). pp. 435–450. Springer (2014)
Bonchi, F., Sobocinski, P., Zanasi, F.: Full abstraction for signal flow graphs. In: Proceedings of the 42nd Annual ACM SIGPLAN Symposium on Principles of Programming Languages (POPL). pp. 515–526 (2015)
Bonchi, F., Sobocinski, P., Zanasi, F.: The calculus of signal flow diagrams I: linear relations on streams. Information and Computation 252, 2–29 (2017)
Coecke, B., Duncan, R.: Interacting quantum observables. In: Proceedings of the 35th international colloquium on Automata, Languages and Programming (ICALP), Part II. pp. 298–310 (2008)
Coecke, B., Kissinger, A.: Picturing Quantum Processes - A first course in Quantum Theory and Diagrammatic Reasoning. Cambridge University Press (2017)
De Nicola, R., Hennessy, M.C.: Testing equivalences for processes. Theoretical Computer Science 34(1-2), 83–133 (1984)
Ghica, D.R.: Diagrammatic reasoning for delay-insensitive asynchronous circuits. In: Computation, Logic, Games, and Quantum Foundations. The Many Facets of Samson Abramsky, pp. 52–68. Springer (2013)
Ghica, D.R., Jung, A.: Categorical semantics of digital circuits. In: Proceedings of the 16th Conference on Formal Methods in Computer-Aided Design (FMCAD). pp. 41–48 (2016)
Ghica, D.R., Lopez, A.: A structural and nominal syntax for diagrams. In: Proceedings 14th International Conference on Quantum Physics and Logic (QPL). pp. 71–83 (2017)
Hoare, C.A.R.: Communicating Sequential Processes. Prentice Hall (1985)
Honda, K., Yoshida, N.: On reduction-based process semantics. Theoretical Computer Science 152(2), 437–486 (1995)
Mac Lane, S.: Categorical algebra. Bulletin of the American Mathematical Society 71, 40–106 (1965)
Mac Lane, S.: Categories for the Working Mathematician. Springer (1998)
Mason, S.J.: Feedback Theory: I. Some Properties of Signal Flow Graphs. MIT Research Laboratory of Electronics (1953)
Milius, S.: A sound and complete calculus for finite stream circuits. In: Proceedings of the 2010 25th Annual IEEE Symposium on Logic in Computer Science (LICS). pp. 421–430 (2010)
Milner, R.: A Calculus of Communicating Systems, Lecture Notes in Computer Science, vol. 92. Springer (1980)
Milner, R., Sangiorgi, D.: Barbed bisimulation. In: Proceedings of the 19th International Colloquium on Automata, Languages and Programming (ICALP). pp. 685–695 (1992)
Morris Jr, J.H.: Lambda-calculus models of programming languages. Ph.D. thesis, Massachusetts Institute of Technology (1969)
Pavlovic, D.: Monoidal computer I: Basic computability by string diagrams. Information and Computation 226, 94–116 (2013)
Pavlovic, D.: Monoidal computer II: Normal complexity by string diagrams. arXiv:1402.5687 (2014)
Plotkin, G.D.: Call-by-name, call-by-value and the \(\lambda \)-calculus. Theoretical Computer Science 1(2), 125–159 (1975)
Rutten, J.J.M.M.: A tutorial on coinductive stream calculus and signal flow graphs. Theoretical Computer Science 343(3), 443–481 (2005)
Rutten, J.J.M.M.: Rational streams coalgebraically. Logical Methods in Computer Science 4(3) (2008)
Selinger, P.: A survey of graphical languages for monoidal categories. Springer Lecture Notes in Physics 13(813), 289–355 (2011)
Shannon, C.E.: The theory and design of linear differential equation machines. Tech. rep., National Defence Research Council (1942)
Willems, J.C.: The behavioural approach to open and interconnected systems. IEEE Control Systems Magazine 27, 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
© 2020 The Author(s)
About this paper
Cite this paper
Bonchi, F., Piedeleu, R., Sobociński, P., Zanasi, F. (2020). Contextual Equivalence for Signal Flow Graphs. In: Goubault-Larrecq, J., König, B. (eds) Foundations of Software Science and Computation Structures. FoSSaCS 2020. Lecture Notes in Computer Science(), vol 12077. Springer, Cham. https://doi.org/10.1007/978-3-030-45231-5_5
Download citation
DOI: https://doi.org/10.1007/978-3-030-45231-5_5
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-45230-8
Online ISBN: 978-3-030-45231-5
eBook Packages: Mathematics and StatisticsMathematics and Statistics (R0)