# Article

MSC: 93A15, 93C65
Full entry | PDF   (0.3 MB)
Keywords:
Petri net; structural property; linear inequality; product incidence matrix
Summary:
This paper presents some structural properties of a generalized Petri net (PN) with an algorithm to determine the (partial) conservativeness and (partial) consistency of the net. A product incidence matrix $A=CC^T$ or $\tilde{A}=C^TC$ is defined and used to further improve the relations among PNs, linear inequalities and matrix analysis. Thus, based on Cramer's Rule, a new approach for the study of the solution of a linear system is given in terms of certain sub-determinants of the coefficient matrix and an efficient algorithm is proposed to compute these sub-determinants. The paper extends the common necessary and/or sufficient conditions for conservativeness and consistency in previous papers and some examples are designed to explain the conclusions finally.
References:
[1] Ahmad, F., Hejiao, H., Xiaolong, W.: Analysis of structure properties of Petri nets. Using Transition Vectors, Inform. Technol. J. 7 (2008), 285-291. DOI 10.3923/itj.2008.285.291
[2] Berthelot, G., Terrat, R.: Petri nets theory for correctness of protocols. IEEE Trans. Commun. COM-30 (1982), 12, 2497-2505. DOI 10.1109/TCOM.1982.1095452 | MR 0687447
[3] Cheng, T., Zeng, W.: Invariant preserving transformations for the verification of place/transition systems. IEEE Trans. Systems, Man, Cybernet. Part A: Systems and Humans 28 (1998), 1, 114-121. DOI 10.1109/3468.650328
[4] Fiedler, M., Pták, V.: On matrices with non-positive off-diagonal elements and positive principal minors. Czechoslovak Math. J. 12 (1962), 382-400. MR 0142565 | Zbl 0131.24806
[5] Liu, G., Jiang, Ch.-J.: Incidence matrix based methods for computing repetitive vectors and siphons of Petri net. J. Inform. Sci. Engrg. 25 (2009), 121-136. MR 2509898
[6] Hefferon, J.: Internet published textbook. 2011. III: Laplaces Expansion, and Topic: Cramers Rule, http://joshua.smcvt.edu/linearalgebra/
[7] Liao, J. L., Wang, M., Yang, C.: A new method for structural analysis of Petri net models based on incidence matrix. J. Inform. Comput. Sci. 8 (2011), 6, 877-884.
[8] Karp, R., Miller, R.: Parallel program schemata. J. Comput. Syst. Sci. 3 (1969), 147-195. DOI 10.1016/S0022-0000(69)80011-5 | MR 0246720 | Zbl 0369.68013
[9] Lien, Y. L.: Termination properties of generalized Petri nets. SIAM J. Comput. 5 (1976), 251-265. DOI 10.1137/0205020 | MR 0419093 | Zbl 0332.68037
[10] Murata, T.: Petri nets: Properties, analysis and applications. Proc. IEEE 77 (1989), 541-580.
[11] Matcovschi, M., Mahulea, C., Pastravanu, O.: Exploring structural properties of Petri nets in MATLAB. Trans. Automat. Control Comput. Sci. XLVII(LI), (2001), 1 - 4, 15-26. Zbl 1240.68148
[12] Xiong, P. Ch., Fan, Y. S., Zhou, M. Ch.: A Petri net approach to analysis and composition of web services. IEEE Trans. Systems, Man, Cybernet. Part A: Systems and Humans 40 (2010), 376-387. DOI 10.1109/TSMCA.2009.2037018
[13] Peterson, J.: Petri Net Theory and the Modelling of Systems. Prentice Hall, 1983. MR 0610984 | Zbl 0461.68059
[14] Rachid, B., Abdellah, E. M.: On the analysis of some structural properties of Petri nets. IEEE Trans. Systems, Man, Cybernet., Part A: Systems and Humans 35 (2005), 784-794. DOI 10.1109/TSMCA.2005.851323
[15] Takano, K., Taoka, S., Yamauchi, M., Watanabe, T.: Two efficient methods for computing Petri net invariants. In: Proc. IEEE Internat. Conf. on Systems, Man, Cybern. 2001, pp. 2717-2722.
[16] Takano, K., Taoka, S., Yamauchi, M., Watanabe, T.: Experimental evaluation of two algorithms for computing Petri net invariants. IEICE Trans. Fundam. E84-A11 (2001), 2871-2880.
[17] Wu, Y., Xie, L. Y., Li, J. D.: New method to identify minimal cut sets using the incidence matrix of Petri nets. China Mech. Engrg. 19 (2008), 1044-1047.
[18] Yahia, C. A., Zerhouni, N.: Structure theory of choice-free Petri nets based on eigenvalues. J. Franklin Inst. 336 (1999), 833-849. DOI 10.1016/S0016-0032(99)00008-3 | MR 1696381 | Zbl 0973.93029
[19] Yahia, C. A., Zerhouni, N., Moudni, A. El, Ferney, M.: Some subclass of Petri nets and the analysis of their structural properties: A new approach. IEEE Trans. Systems, Man, Cybernet. Part A: Systems and Humans 29 (1999), 164-172. DOI 10.1109/3468.747851
[20] Yamauchi, M., Wakuda, M., Taoka, S., Watanabe, T.: A fast and space-saving algorithm for computing invariants of Petri nets. In: Proc. IEEE Internat. Conf. Systems, Man, Cybernet. 1999, pp. 866-871.
[21] Zurawski, R.: Petri net models, functional abstractions, and reduction techniques: Applications to the design of automated manufacturing systems. IEEE Trans. Industr. Electron. 52 (2005), 595-609. DOI 10.1109/TIE.2005.844225

Partner of