Informatics and Applications
2024, Volume 18, Issue 1, pp 11-17
ALGEBRAIC SPECIFICATION OF GRAPH COMPUTATIONAL STRUCTURES
Abstract
The previously proposed generalized approach to algebraic specification of distributed systems is developed based on the novel category-theoretic construction called graphalgebra. The graphalgebraic specification is based upon a directed multigraph, the edges of which represent computational operations performed in the nodes of the system and the vertices denote the data exchange ports between the components. Changing the system architecture during the life cycle leads to changes in the graph shape, computation algorithms, and data exchange contents. For a formal description of such changes, a graph transformation technique for graphalgebras is proposed. A novel category-theoretic construction called flexible graphalgebra is introduced which appeared to be closely related to the well-known monad of diagrams. A functor is presented that produces all categories of flexible graphalgebras from their signatures. The theoretical results are illustrated by examples from the field of automatic synthesis of neural network architecture by step-by-step transformations.
[+] References (11)
- Kovalyov, S. P. 2004. Formal'nyy podkhod k razrabotke programmnykh sistem [Formal approach to software systems development]. Novosibirsk: NSU. 180 p.
- Gurevich, Y. 1995. Evolving algebras 1993: Lipari guide. Specification and validation methods. Oxford: Oxford University Press. 9-36.
- Kovalyov, S. P. 2022. Algebraicheskaya spetsifikatsiya grafovykh vychislitel'nykh struktur [Algebraic specification of graph computational structures]. Informatika i ee Primeneniya - Inform. Appl. 16(1):2-9. doi: 10.14357/ 19922264220101. EDN: GXHPZI.
- Cai, H., T. Chen, W. Zhang, Y. Yu, and J. Wang. 2018. Efficient architecture search by network transformation. 32th AAAI Conference "Artificial Intelligence" Proceedings. Eds. S. A. McIlraith and K. Q. Weinberger. Palo Alto, CA: AAAI Press. 2787-2794.
- Mens, T., J. Magee, and B. Rumpe. 2010. Evolving software architecture descriptions of critical systems. Computer 43(5):42-48. doi: 10.1109/MC.2010.136.
- Barr, M., and C. Wells. 1990. Category theory for computing science. London: Prentice Hall. 538 p.
- Kovalyov, S. P. 2017. Metody teorii kategoriy v model'no- orientirovannoy sistemnoy inzhenerii [Methods of category theory in model-based systems engineering]. Informatika i ee Primeneniya - Inform. Appl. 11(3):42-50. doi: 10.14357/19922264170305. EDN: ZGIGGD.
- Kovalyov, S. P. 2018. Teoriya kategoriy kak matematicheskaya pragmatika model'no-orientirovannoy sistemnoy inzhenerii [Category theory as a mathematical pragmatics of model-based systems engineering]. Informatika i ee Primeneniya - Inform. Appl. 12(1):95-104. EDN: YTTRFC.
- Ad‚amek, J., H. Herrlich, and G. E. Strecker. 1990. Abstract and concrete categories. New York, NY: John Wiley. 507 p.
- Mac Lane, S. 1978. Categories for the working mathematician. New York, NY: Springer. 317 p.
- Semenov, P. V., R. P. Semishkur, and I. A. Dyachenko. 2019. Kontseptual'naya model' realizatsii tekhnologii "tsifrovykh dvoynikov" dlya predpriyatiy neftegazovogo kompleksa [Conceptual model of digital twin technology implementation for oil and gas industry]. Gazovaya promyshlennost' [Gas Industry] 7(787):24-30. EDN: EZXDVJ.
[+] About this article
Title
ALGEBRAIC SPECIFICATION OF GRAPH COMPUTATIONAL STRUCTURES
Journal
Informatics and Applications
2024, Volume 18, Issue 1, pp 11-17
Cover Date
2024-04-10
DOI
10.14357/19922264240102
Print ISSN
1992-2264
Publisher
Institute of Informatics Problems, Russian Academy of Sciences
Additional Links
Key words
algebraic specification; distributed system; architecture evolution; category theory; graphalgebra; monad of diagrams
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
|