Informatics and Applications
2022, Volume 16, Issue 1, pp 29
ALGEBRAIC SPECIFICATION OF GRAPH COMPUTATIONAL STRUCTURES
Abstract
Problems of composing algebraic specifications for computational structures represented by data flow graphs are considered. The evolution of algebraic program specification tools is briefly outlined, from manysorted algebra via coalgebra to a categorytheoretical construction of dialgebra capable of describing interactive computing nodes. As a next step, a novel categorytheoretical construction called graphalgebra is proposed which allows combining dialgebras into arbitrary directed multigraphs whose edges represent computational operations at nodes and whose vertices describe data exchanged between nodes. Examples of graphalgebraic specifications for neural networks and multiprocessor computational systems are given. The method of building categories of graphalgebras via universal constructions is described. For a computational structure of the system of systems kind consisting of graph structures, methods of hierarchical construction of an algebraic specification from the specifications of components are proposed.
[+] References (16)
 Cleaveland, R., and S. A. Smolka. 1996. Strategic directions in concurrency research. ACM Comput. Surv. 28(4):607625.
 Mac Lane, S. 1978. Categories for the working mathematician. New York, NY: Springer. 317 p.
 Abramsky, S., S.J. Gay, and R. Nagarajan. 1995. Interaction categories and foundations of typed concurrent programming. Deductive program design. Ed. M. Broy. NATO ASI ser. F SpringerVerlag. 35113.
 Bergstra, J. A., and C. A. Middelburg. 2019. Using Hoare logic in a process algebra setting. arXiv.org. 24 p. Available at: https://arxiv.org/abs/1906.04491 (accessed December 17, 2021).
 Stewart, R., B. Berthomieu, P. Garcia, I. Ibrahim, G. Michaelson, and A. Wallace. 2019. Verifying parallel dataflow transformations with model checking and its application to FPGAs. J. Syst. Architect. 101:101657.
 Kovalyov, S. P. 2004. Formal'nyy podkhod k razrabotke programmnykh sistem [Formal approach to software systems development]. Novosibirsk: NGU. 180 p.
 Jacobs, B., and J. Rutten. 1997. Atutorial on (co)algebras and (co)induction. EATCS Bulletin 62:222259.
 Poll, E., and J. Zwanenburg. 2001. From algebras and coalgebras to dialgebras. Electronic Notes Theoretical Computer Science 44(1):289307.
 Adamek, J., H. Herrlich, and G.E. Strecker. 1990. Abstract and concrete categories. New York, NY: John Wiley 507 p.
 Looks, M., M. Herreshoff, D. Hutchins, and P. Norvig. 2017. Deep learning with dynamic computation graphs. arXiv.org. Available at: https://arxiv.org/abs/1702.02181 (accessed December 17, 2021).
 Carriero, N.J., D. Gelernter, T. G. Mattson, and A. H. Sherman. 1994. The Linda alternative to message passing systems. ParallelComput. 20(4):633655.
 Burmeister, P. 1993. Partial algebras  an introductory survey. Algebras and orders. Eds. I. G. Rosenberg and G. Sabidussi. NATO ASI ser. C. Kluwer Academic Publs. 389:170.
 Comma category. Available at: https://ncatlab.org/nlab/ show/comma+category (accessed December 17, 2021).
 Kovalyov, S. P. 2021. Metody teorii kategoriy v tsifrovom proektirovanii geterogennykh kiberfizicheskikh sistem [Methods of category theory in digital design of heterogeneous cyberphysical systems]. Informatika i ee Prime neniya  Inform. Appl. 15(1):2329.
 Fawaz, H. I., G. Forestier, J. Weber, L. Idoumghar, and P. Muller. 2019. Deep neural network ensembles for time series classification. Joint Conference (International) on Neural Networks Proceedings. Piscataway, NJ: IEEE. 8852316. 6 p. doi: 10.1109/IJCNN.2019.8852316.
 Kovalyov, S. P 2018. Teoriya kategoriy kak matematicheskaya pragmatika model'nooriyentirovannoy sistemnoy inzhenerii [Category theory as a mathematical pragmatics of modelbased systems engineering]. Informatika i ee Primeneniya  Inform. Appl. 12(1):95104.
[+] About this article
Title
ALGEBRAIC SPECIFICATION OF GRAPH COMPUTATIONAL STRUCTURES
Journal
Informatics and Applications
2022, Volume 16, Issue 1, pp 29
Cover Date
20220330
DOI
10.14357/19922264220101
Print ISSN
19922264
Publisher
Institute of Informatics Problems, Russian Academy of Sciences
Additional Links
Key words
algebraic specification; graph computational structure; system of systems; category theory; dialebra; graphalgebra; pullback
Authors
S. P. Kovalyov
Author Affiliations
V. A. Trapeznikov Institute of Control Sciences of the Russian Academy of Sciences, 65 Profsoyuznaya Str., Moscow 117997, Russian Federation
