Geodesic
Analysis of structural properties of Petri nets based on product incidence matrix
Kybernetika, Tome 49 (2013) no. 4, pp. 601-618 Cet article a éte moissonné depuis la source Czech Digital Mathematics Library

Voir la notice de l'article

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.
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.
Classification : 93A15, 93C65
Keywords: Petri net; structural property; linear inequality; product incidence matrix 
@article{KYB_2013_49_4_a6,
     author = {Ji, Guangyou and Wang, Mingzhe},
     title = {Analysis of structural properties of {Petri} nets based on product incidence matrix},
     journal = {Kybernetika},
     pages = {601--618},
     year = {2013},
     volume = {49},
     number = {4},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/KYB_2013_49_4_a6/}
}
TY  - JOUR
AU  - Ji, Guangyou
AU  - Wang, Mingzhe
TI  - Analysis of structural properties of Petri nets based on product incidence matrix
JO  - Kybernetika
PY  - 2013
SP  - 601
EP  - 618
VL  - 49
IS  - 4
UR  - http://geodesic.mathdoc.fr/item/KYB_2013_49_4_a6/
LA  - en
ID  - KYB_2013_49_4_a6
ER  - 
%0 Journal Article
%A Ji, Guangyou
%A Wang, Mingzhe
%T Analysis of structural properties of Petri nets based on product incidence matrix
%J Kybernetika
%D 2013
%P 601-618
%V 49
%N 4
%U http://geodesic.mathdoc.fr/item/KYB_2013_49_4_a6/
%G en
%F KYB_2013_49_4_a6
Ji, Guangyou; Wang, Mingzhe. Analysis of structural properties of Petri nets based on product incidence matrix. Kybernetika, Tome 49 (2013) no. 4, pp. 601-618. http://geodesic.mathdoc.fr/item/KYB_2013_49_4_a6/

[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

[2] Berthelot, G., Terrat, R.: Petri nets theory for correctness of protocols. IEEE Trans. Commun. COM-30 (1982), 12, 2497-2505. | DOI | MR

[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

[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 | Zbl

[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

[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 | MR | Zbl

[9] Lien, Y. L.: Termination properties of generalized Petri nets. SIAM J. Comput. 5 (1976), 251-265. | DOI | MR | Zbl

[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

[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

[13] Peterson, J.: Petri Net Theory and the Modelling of Systems. Prentice Hall, 1983. | MR | Zbl

[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

[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 | MR | Zbl

[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

[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