Kybernetika 49 no. 4, 601-618, 2013

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

Guangyou Ji and Mingzhe Wang

Abstract:

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.

Keywords:

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

Classification:

93C65, 93A15

References:

  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, http://joshua.smcvt.edu/linearalgebra/.   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