Matrix Approach to Solving Reachability Problems in Stochastic Petri Nets

Abstract

The purpose of the research was to develop the theory of stochastic Petri nets and consider its practical application when studying discrete systems. The paper considers the possibility of solving the reachability problem in stochastic Petri nets by means of matrix equations widely used in Petri nets; describes the stages and features of generating matrix equations for stochastic networks; formulates the rules for introducing virtual elements, i.e., positions and transitions, into the stochastic Petri net to generate and solve matrix equations. Stochastic Petri nets different in structure and composition were used to explore the possibility of applying matrix equations. Findings of the research show that the reachability of the required states of the networks is determined through the firing of transitions, which are the solution of the matrix equation. Within the study, we interpreted the obtained results and developed an algorithm that allowed us to validate the assumption made and visually determine the restrictions on the use of matrix equations for various initial states of the simulated system. The results of the proposed algorithm are presented in graphical form on the examples of stochastic Petri nets that model the process of forensic handwriting analysis. The conclusion is made about the applicability of matrix equations in stochastic Petri nets and the need for further research in this area

Please cite this article in English as:

Zvyagin D.S., Pyankov O.V., Kopylov A.N. Matrix approach to solving reachability problems in stochastic Petri nets. Herald of the Bauman Moscow State Technical University, Series Natural Sciences, 2022, no. 3 (102), pp. 4--16 (in Russ.). DOI: https://doi.org/10.18698/1812-3368-2022-3-4-16

References

[1] Men’shikh V.V., Lunev Yu.S. Simulation of destabilizing factors influence on distributed information systems by Petri nets. Autom. Remote Control, 2011, vol. 72, no. 11, pp. 2417--2424. DOI: https://doi.org/10.1134/S0005117911110166

[2] Kotov V.E. Seti Petri [Petri nets]. Moscow, Nauka Publ., 1984.

[3] Leskin A.A., Maltsev P.A., Spiridonov A.M. Seti Petri v modelirovanii i upravlenii [Petri nets in modeling and control]. Leningrad, Nauka Publ., 1989.

[4] Peterson J.L. Petri net theory and the modeling of systems. Englewood Cliffs, 1981.

[5] Pyankov O.V., Zvyagin D.S. Modeling the production process of forensic handwriting expertise using stochastic Petri nets. The Bulletin of Voronezh Institute of the Ministry of Internal Affairs of Russia, 2020, no. 1, pp. 154--163 (in Russ.).

[6] Bellman R.E. Introduction to matrix analysis. McGraw-Hill, 1970.

[7] Waerden B.L. Algebra. Ungar, 1970.

[8] Vygodskiy M.Ya. Spravochnik po vysshey matematike [Handbook of higher mathematics]. Moscow, Nauka Publ., 1977.

[9] Gantmakher F.R. Teoriya matrits [Matrix theory]. Moscow, FIZMATLIT Publ., 2010.

[10] Ilin V.A., Poznyak E.G. Lineynaya algebra [Linear algebra]. Moscow, FIZMATLIT Publ., 2005.

[11] Jensen K., Kristensen L.M. Coloured Petri nets. Modelling and validation of concurrent systems. Berlin, Heidelberg, Springer, 2009. DOI: https://doi.org/10.1007/b95112

[12] Birkhoff G., Bartee T.C. ‎ Modern applied algebra. McGraw-Hill, 1970.

[13] Gmurman V.E. Teoriya veroyatnostey i matematicheskaya statistika [Theory of probability and mathematical statistics]. Moscow, Vysshaya shkola Publ., 1972.

[14] Golub G.H., van Loan C.F. Matrix computations. JHU Press, 1996.

[15] Zvyagin D.S. Conditions for application of the matrix approach to stochastic Petri nets. The Bulletin of Voronezh Institute of the Ministry of Internal Affairs of Russia, 2021, no. 3, pp. 101--110 (in Russ.).