ABSTRACTS OF ARTICLES OF THE JOURNAL "INFORMATION TECHNOLOGIES".
No. 4. Vol. 30. 2024

DOI: 10.17587/it.30.206-213

V. P. Kulagin, Dr. Sc., Professor,
Moscow University of Technical Communications and Informatics, Moscow, Russian Federation,
N. D. Muravyev, Postgraduate,
RTU MIREA, Moscow, Russian Federation

Generation of PN-Model Synthesis Programs with Restrictions

The paper proposes a modified algorithm for generating programs for the synthesis of network models expressed in terms of Petri nets [8]. The algorithm is based on the use of boundedly growing strings and the ability to generate them in lexicographic order. To reduce the number of possible synthesis programs, the introduction of limiting conditions imposed on the set partition tree is considered. Taking into account the imposed restrictions, a new tree of smaller dimension is built, which also preserves the lexicographic order of the limitedly growing strings it contains. A comparative assessment of the effectiveness of a new algorithm for generating boundedly growing strings with restrictions and a standard algorithm without restrictions, which is described by D. Knuth, is given. The proposed algorithm can be used to solve problems of synthesizing models of complex computational structures, building parallel systems, parallelizing algorithms and solving other problems related to the creation of efficient distributed systems.
Keywords: Petri net, restricted growth string, Bell number, a set partition, synthesis program, a set partition tree

P. 206-213

References

1. Kotov V. E. Petri Nets, Moscow, Nauka, 1984, 160 p. (in Russian).
2. Peterson Dzh. Petri Net Theory and the Modeling of Systems, Moscow, Mir, 1984, 264 p. (in Russian).
3. Marahovskij V. B., Rozenblyum L. Ya., Yakovlev A. V. Simulation of parallel processes. Petri nets. Course for system architects, programmers, system analysts, designers of complex system management, SPb., Professionalnaya literatura, AjTi-Podgotovka, 2014, 400 p. (in Russian).
4. Butler J. T., Sasao T. A set partition number system, Australasian Journal of Combinatorics, 2016, vol. 65, no. 2, pp. 152—169.
5. Freitas Braian, Basilio J. Online Fault Diagnosis of Discrete Event Systems Modeled by Labeled Petri Nets Using Labeled Priority Petri Nets, IFAC-PapersOnLine, 2022, vol. 55, pp. 329—336.
6. Staines Anthony. Concurrency and Petri Net Models, International Journal of Circuits, systems and signal Processing, 2022, vol. 16, pp. 852—858.
7. Kurt J., Susanna D., Maciej K. Transactions on Petri Nets and Other Models of Concurrency IV (Lecture Notes in Computer Science), Springer-Verlag, 2011, vol. 6550, pp. 225.
8. Kurt J., Susanna D., Jetty K. Transactions on Petri Nets and Other Models of Concurrency V, Lecture Notes in Computer Science, Springer-Verlag, 2012, vol. 6900, pp. 293.
9. Kurt J., Jetty K., Giuliana F. et al. Transactions on Petri Nets and Other Models of Concurrency VI, Lecture Notes in Computer Science, Springer-Verlag, 2012, vol. 7400, pp. 365.
10. Petri Nets World — Petri Nets World: Online Services for the International Petri Nets Community, available at: http://www. informatik.uni-hamburg.de/TGI/PetriNets/
11. Kulagin V. P., Dubinin V. N. Structural Analysis of Petri Nets, Informacionnye Tehnologii, 2016, vol. 22, no. 1, pp. 3—13 (in Russian).
12. Leskin A. A., Malcev P. A., Spiridonov A. M. Petri nets in modeling and control, Leningrad, Nauka, 1989, 135 p. (in Russian).
13. Ankundinov G. I. Synthesis of the structure of complex objects. Logic-combinatorial approach, Leningrad, LGU, 1986. 258 p. (in Russian).
14. Skornyakov L. A. Elements of the theory of structures, Moscow, Nauka, 1982, 149 p. (in Russian).
15. Birkgof G. Structure theory, Moscow, Inostrannaya literatura, 1952. 407 p. (in Russian).
16. Kulagin V. P. Tensor methods of research structures of Petri nets, Informacionnye Tehnologii, 2015, vol. 21, no. 2, pp. 83—94 (in Russian).
17. Kulagin V. P., Malih E. S. Design of matrix computing structures using petri nets, Informacionnye Tehnologii, 2019, vol. 25, no. 5, pp. 271—283 (in Russian).
18. Kulagin V. P. Tensor methods of analysis and synthesis of complex computing systems, Tutorial, Moscow, Publishing house of Moskovskii Gosudarstvennii Institute electronici i matematici, 1998, pp. 102 (in Russian).
19. Kulagin V. P. Methods for constructing transformation tensors for network models of complex systems, Informatization of education and science, 2015, no. 4 (28), pp. 133—147.
20. Roughgarden T. Algorithms Illuminated. Algorithms for NP-Hard Problems. SPb., Piter, 2021, 304 pp. (in Russian).
21. Kulagin V. P., Muravyev N. D. A method for synthesizing net models of computational structures based on the properties of a restricted growth string, Problems of informatics in education, management, economics and technics: digest of articles XXII International scientific and technical conference, Penza, 09—10 December 2022 year, Penza, Avtonomnaya nekomercheskaya nauchno-obrazovatelnaya organizaciya "Privolzhskii Dom znanii", 2022, 40—44 pp. (in Russian).
22. Knuth D. E. The Art of computer programming, volume 4A. Combinatorical Algorithms, Part 1, Moscow, OOO "I. D. Williams", 2013, pp. 960 (in Russian).

To the contents