Abstract:
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.
