Computational nanotechnologyComputational nanotechnologyComputational nanotechnology2313-223X2587-9693YUR-VAK38019810.33693/2313-223X-2025-12-4-178-186GNHCQHINFORMATICS AND INFORMATION PROCESSINGИНФОРМАТИКА И ИНФОРМАЦИОННЫЕ ПРОЦЕССЫResearch ArticleDecomposition of complex systems represented by Petri netsДекомпозиция сложных систем, выраженных в терминах сетей Петри592100503001558-1128MuravievNikolay D.МуравьевНиколай Дмитриевич
Russian Federation

postgraduate student

аспирант

muravev.nd@mail.ru569120077002438-4900KulaginVladimir P.КулагинВладимир Петрович
Russian Federation

Dr. Sci. (Eng.), Professor

доктор технических наук, профессор

vpkulagin@mail.ruMoscow Technical University of Communications and Informatics (MTUCI)Московский технический университет связи и информатики (МТУСИ)12122025124Computational nanotechnologyComputational nanotechnology17818602022026Copyright ©; 2025, Yur-VAKCopyright ©; 2025, Юр-ВАК2025Yur-VAKЮр-ВАКhttps://www.urvak.ru/contacts/https://journals.rcsi.science/2313-223X/article/view/380198

This paper addresses the problem of decomposition of complex systems represented as Petri nets, with the aim of optimizing the synthesis procedure for new parallel systems. An improved approach is proposed, combining Johnson’s algorithm with the depth-first search method. Johnson’s algorithm is applied for the efficient detection of elementary cycles, which makes it possible to overcome the limitations of the traditional matrix-based method, characterized by high computational and spatial complexity, as well as the inability to guarantee the extraction of elementary cycles of a given length. An adapted depth-first search algorithm is used to identify linear fragments of acyclic Petri nets. An analytical and experimental comparison of the proposed algorithms with well-known counterparts has been carried out on both complete and sparse Petri nets. The experimental data indicates a significant advantage of Johnson’s algorithm when applied to sparse Petri net structures, manifested in increased execution speed and completeness in detecting elementary cycles. The proposed approach demonstrates a substantial reduction in time costs at the decomposition stage and contributes to the creation of conditions (a knowledge base) that restrict the set of synthesized structures and simplify subsequent stages of parallel system design. The obtained results confirm the practical efficiency and applicability of the proposed Petri net decomposition methods in the synthesis of complex system structures.

Статья посвящена проблеме декомпозиции сложных систем, представленных в виде сетей Петри, с целью оптимизации процедуры синтеза новых параллельных систем. Предлагается улучшенный подход, объединяющий алгоритм Джонсона и метод поиска в глубину. Алгоритм Джонсона применяется для эффективного поиска элементарных циклов, что позволяет преодолеть ограничения традиционного матричного метода, характеризующегося высокой вычислительной и пространственной сложностью, а также невозможностью гарантировать выделение элементарных циклов заданной длины. Для нахождения линейных фрагментов ацикличных сетей Петри используется адаптированный алгоритм поиска в глубину. Проведено аналитическое и экспериментальное сравнение предложенных алгоритмов с известными аналогами на полных и разряженных сетях Петри. Экспериментальные данные показывают значительное преимущество алгоритма Джонсона при работе с разряженными структурами сетей Петри, выражающееся в увеличении скорости выполнения и в полноте обнаружения элементарных циклов. Предлагаемый подход демонстрирует существенное сокращение временных затрат на этапе декомпозиции и способствует созданию условий (базы знаний), ограничивающих множество синтезируемых структур и упрощающих последующие этапы проектирования параллельных систем. Полученные результаты подтверждают практическую эффективность и применимость предложенных методов декомпозиции сетей Петри в задачах синтеза структур сложных систем.

Petri netsynthesis of computational structuresdecompositionJohnson’s algorithmTarjan’s algorithmсеть Петрисинтез вычислительных структурдекомпозицияалгоритм Джонсонаалгоритм ТарьянаChristofides N. Graph theory. An algorithmic approach. Moscow: Mir, 1978. 432 p.Кристофидес Н. Теория графов. Алгоритмический подход. М.: Мир, 1978. 432 с.Kulagin V.P. Methods for constructing tensor transformation for network models of complex systems. Informatization of Education and Science. 2015. Vol. 28. No. 4. Pp. 133–147. (In Rus.)Кулагин В.П. Методы построения тензоров преобразования для сетевых моделей сложных систем // Информатизация образования и науки. 2015. Т. 28. № 4. С. 133–147.Kulagin V.P. Tensor methods of research structures of Petri nets. Information Technologies. 2015. Vol. 21. No. 2. Pp. 83—94. (In Rus.)Кулагин В.П. Тензорные методы исследования структуры сетей Петри // Информационные технологии. 2015. T. 21. № 2. С. 83–94.Kulagin V.P., Dubinin V.N. Structural analysis of Petri nets. Information Technologies. 2016. Vol. 22. No. 4. Pp. 3–13. (In Rus.)Кулагин В.П., Дубинин В.Н. Структурный анализ сетей Петри // Информационные технологии. 2016. Т. 22. № 4. С. 3–13.Kulagin V.P., Malych E.S. Design of matrix computing structures using Petri nets. Information Technologies. 2019. Vol. 25. No. 5. Pp. 271–283. (In Rus.)Кулагин В.П., Малых Е.С. Проектирование матричных вычислительных структур с использованием сетей Петри // Информационные технологии. 2019. Т. 25. № 5. С. 271–283.Kulagin V.P., Muravyev N.D. Generation of PN-model synthesis programs with restrictions. Information Technologies. 2024. Vol. 30. No. 4. Pp. 206–213. (In Rus.)Кулагин В.П., Муравьев Н.Д. Генерация программ синтеза моделей, основанных на сетях Петри, с ограничениями // Информационные технологии. 2024. Т. 30. № 4. С. 206–213.Kulagin V.P., Muraviev N.D. A method for synthesizing net models of computational structures based on the properties of a restricted growth string. In: Problems of informatics in education, management, economics and technics. Collection of articles from the XXII International Scientific and Technical Conference (Penza, December 9–10, 2022).Penza: Volga House of Knowledge, 2022. Pp. 40–44.Кулагин В.П., Муравьев Н.Д. Метод синтеза сетевых моделей вычислительных структур, основанный на свойствах ограниченно растущей строки // Проблемы информатики в образовании, управлении, экономике и технике: сборник статей XXII Междунар. науч.-техн. конф. (Пенза, 9–10 декабря 2022 г.). Пенза: Приволжский Дом знаний, 2022. С. 40–44.Bukowiec A. et al. Implementation of algorithm of petri nets distributed synthesis into FPGA. International Journal of Electronics and Telecommunications. 2013. Vol. 59. No. 4. Pp. 317–324.Bukowiec A. et al. Implementation of algorithm of petri nets distributed synthesis into FPGA // International Journal of Electronics and Telecommunications. 2013. Vol. 59. No. 4. Pp. 317–324.Bukowiec A., Adamski M. Synthesis of macro Petri nets into FPGA with distributed memories. International Journal of Electronics and Telecommunications. 2012. Vol. 58. No. 4. Pp. 403–410.Bukowiec A., Adamski M. Synthesis of macro Petri nets into FPGA with distributed memories // International Journal of Electronics and Telecommunications. 2012. Vol. 58. No. 4. Pp. 403–410.Bukowiec A., Mroz P. An FPGA synthesis of the distributed control systems designed with petri nets. In: IEEE 3rd International Conference Networked Embedded Systems for Every Application (NESEA). 2012. Liverpool, UK.Bukowiec A., Mroz P. An FPGA synthesis of the distributed control systems designed with petri nets // IEEE 3rd International Conference Networked Embedded Systems for Every Application (NESEA). 2012. Liverpool, UK.Gomes L. et al. From Petri net models to VHDL implementation of digital controllers. In: The 33rd Annual Conference of the IEEE Industrial Electronics Society IECON 2007. Taipei, Taiwan, 2007.Gomes L. et al. From Petri net models to VHDL implementation of digital controllers // The 33rd Annual Conference of the IEEE Industrial Electronics Society IECON 2007. Taipei, Taiwan, 2007.Johnson D.B. Finding all the elementary circuits of a directed graph. SIAM Journal on Computing. 1975. Vol. 4. No. 1. Pp. 77–84.Johnson D.B. Finding all the elementary circuits of a directed graph // SIAM Journal on Computing. 1975. Vol. 4. No. 1. Pp. 77–84.Soto E., Pereira M. Implementing a Petri net specification in a FPGA using VHDL. Design of Embedded Control Systems. Springer, New York, 2005. Pp. 167–174.Tiernan J.C. An efficient search algorithm to find the elementary circuits of a graph. Communications of the ACM. 1970. Vol. 13. No 12. Pp. 722–726.Tiernan J.C. An efficient search algorithm to find the elementary circuits of a graph // Communications of the ACM. 1970. Vol. 13. No 12. Pp. 722–726.Weinblatt H. A new search algorithm for finding the simple cycles of a finite directed graph. Journal of the ACM (JACM). 1972. Vol. 19. No. 1. Pp. 43–56.Weinblatt H. A new search algorithm for finding the simple cycles of a finite directed graph // Journal of the ACM (JACM). 1972. Vol. 19. No. 1. Pp. 43–56.