Informatics and Applications
2022, Volume 16, Issue 1, pp 2-9
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 many-sorted algebra via coalgebra to a category-theoretical construction of dialgebra capable of describing interactive computing nodes. As a next step, a novel category-theoretical 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):607-625.
- 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 Springer-Verlag. 35-113.
- 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:222-259.
- Poll, E., and J. Zwanenburg. 2001. From algebras and coal-gebras to dialgebras. Electronic Notes Theoretical Computer Science 44(1):289-307.
- 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):633-655.
- 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:1-70.
- 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 cyber-physical systems]. Informatika i ee Prime- neniya - Inform. Appl. 15(1):23-29.
- 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'no-oriyentirovannoy sistemnoy inzhenerii [Category theory as a mathematical pragmatics of model-based systems engineering]. Informatika i ee Primeneniya - Inform. Appl. 12(1):95-104.
[+] About this article
Title
ALGEBRAIC SPECIFICATION OF GRAPH COMPUTATIONAL STRUCTURES
Journal
Informatics and Applications
2022, Volume 16, Issue 1, pp 2-9
Cover Date
2022-03-30
DOI
10.14357/19922264220101
Print ISSN
1992-2264
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
|