Kybernetika 49 no. 4, 601-618, 2013

Analysis of structural properties of Petri nets based on product incidence matrix

Guangyou Ji and Mingzhe Wang


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.


Petri net, structural property, linear inequality, product incidence matrix


93C65, 93A15


  1. F. Ahmad, H. Hejiao and W. Xiaolong: Analysis of structure properties of Petri nets. Using Transition Vectors, Inform. Technol. J. 7 (2008), 285-291.   CrossRef
  2. G. Berthelot and R. Terrat: Petri nets theory for correctness of protocols. IEEE Trans. Commun. COM-30 (1982), 12, 2497-2505.   CrossRef
  3. T. Cheng and W. Zeng: 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.   CrossRef
  4. M. Fiedler and V. Pták: On matrices with non-positive off-diagonal elements and positive principal minors. Czechoslovak Math. J. 12 (1962), 382-400.   CrossRef
  5. G. Liu and Ch.-J. Jiang: Incidence matrix based methods for computing repetitive vectors and siphons of Petri net. J. Inform. Sci. Engrg. 25 (2009), 121-136.   CrossRef
  6. J. Hefferon: Internet published textbook. 2011. III: Laplaces Expansion, and Topic: Cramers Rule,   CrossRef
  7. J. L. Liao, M. Wang and C. Yang: A new method for structural analysis of Petri net models based on incidence matrix. J. Inform. Comput. Sci. 8 (2011), 6, 877-884.   CrossRef
  8. R. Karp and R. Miller: Parallel program schemata. J. Comput. Syst. Sci. 3 (1969), 147-195.   CrossRef
  9. Y. L. Lien: Termination properties of generalized Petri nets. SIAM J. Comput. 5 (1976), 251-265.   CrossRef
  10. T. Murata: Petri nets: Properties, analysis and applications. Proc. IEEE 77 (1989), 541-580.   CrossRef
  11. M. Matcovschi, C. Mahulea and O. Pastravanu: Exploring structural properties of Petri nets in MATLAB. Trans. Automat. Control Comput. Sci. XLVII(LI), (2001), 1 - 4, 15-26.   CrossRef
  12. P. Ch. Xiong, Y. S. Fan and M. Ch. Zhou: 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.   CrossRef
  13. J. Peterson: Petri Net Theory and the Modelling of Systems. Prentice Hall, 1983.   CrossRef
  14. B. Rachid and E. M. Abdellah: On the analysis of some structural properties of Petri nets. IEEE Trans. Systems, Man, Cybernet., Part A: Systems and Humans 35 (2005), 784-794.   CrossRef
  15. K. Takano, S. Taoka, M. Yamauchi and T. Watanabe: Two efficient methods for computing Petri net invariants. In: Proc. IEEE Internat. Conf. on Systems, Man, Cybern. 2001, pp. 2717-2722.   CrossRef
  16. K. Takano, S. Taoka, M. Yamauchi and T. Watanabe: Experimental evaluation of two algorithms for computing Petri net invariants. IEICE Trans. Fundam. E84-A11 (2001), 2871-2880.   CrossRef
  17. Y. Wu, L. Y. Xie and J. D. Li: New method to identify minimal cut sets using the incidence matrix of Petri nets. China Mech. Engrg. 19 (2008), 1044-1047.   CrossRef
  18. C. A. Yahia and N. Zerhouni: Structure theory of choice-free Petri nets based on eigenvalues. J. Franklin Inst. 336 (1999), 833-849.   CrossRef
  19. C. A. Yahia, N. Zerhouni, A. El Moudni and M. Ferney: 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.   CrossRef
  20. M. Yamauchi, M. Wakuda, S. Taoka and T. Watanabe: A fast and space-saving algorithm for computing invariants of Petri nets. In: Proc. IEEE Internat. Conf. Systems, Man, Cybernet. 1999, pp. 866-871.   CrossRef
  21. R. Zurawski: Petri net models, functional abstractions, and reduction techniques: Applications to the design of automated manufacturing systems. IEEE Trans. Industr. Electron. 52 (2005), 595-609.   CrossRef