Summary

Proceedings of the 2013 International Symposium on Nonlinear Theory and its Applications

2013

Session Number:C4L-C

Session:

Number:475

A Method for Reachability Problems of P/T Petri Nets using Algebraic Approach

Masahiro Osogami,  Teruya Yamanishi,  Katsuji Uosaki,  

pp.475-478

Publication Date:

Online ISSN:2188-5079

DOI:10.15248/proc.2.475

PDF download (290.7KB)

P/T Petri nets are one of the useful models for discrete event systems. And a firing count vector for transitions is one of the key concepts to describe and evaluate algebraically their behavior. To consider the reachability, from an initial state called an initial marking, M₀ to destination state called a destination marking M_d are the fundamental problems of Petri nets. There are some methods to solve such reachability problems. One method is to use the coverability(reachability) tree, but the method requires a huge amount of calculation in general. On the other hand, the method to use matrix equations and reduction techniques has the advantage, because the method can utilise the algebraic equation properties of Petri nets. In this paper, we proposed an algebraic approach to reachability problems using Fourier-Motzkin method. Not only particular solutions and elementary T-invariants are obtained from the augmented system of state equation by Fourier-Motzkin method, but also the expansion coefficients of the nonnegative integer solution to represent state equations as Ax = b can be obtained by the same algorithm of the Fourier-Motzkin method.

[1] T. Murata, “Petri nets: Properties, analysis and applications,” Proc. IEEE, vol.77, no.4, pp.451-580, 1989.

[2] C. Giraut and R. Valk, Petri Nets for Systems Engineering, A Guide to Modeling, Verification, and Applications, pp.53-72 and pp.278-316, Springer-Verlag, Berlin, Heidelberg, 2003.

[3] A. E. Kotsin and S. A. Tchoudaikina, “Yet another reachability algorithm for Petri nets,” SIGACT News, vol.29, no.4, pp.98-110, 1998.

[4] A. Hiramitsu, M. Takata, K. Inaba, T. Yoshida, T. Matsumoto, and S. Moro, “A new algorithm of executability of a solution of state equation for P/T Petri net,” IEICE Tech. Rep., CAS2001-64 or CST2001-17, Nov. 2001.

[5] A. Muraya, T. Matsumoto, S. Moro, and H. Hasegawa, “All fundamental particular solutions are needed to express an arbitrary firing count vector in Petri nets,” IEICE Trans. Fundamentals, Vol.E88-A, No.1, pp.399-404, Jan. 2005.

[6] J. Martinez and M. Silva, “A simple and fast algorithm to obtain all invariants of a generalized Petri net,” Procs. of Second European Workshop on Application and Theory of Petri Nets, Informatik Fachberichte 52, pp.301-310, Springer Publishing Company, Berlin, 1982.

[7] M. Takata, T. Matsumoto, and S. Moro, “A new algorithm to derive generators for both invariants and particular solutions of state equation for a P/T Petri net—Extended Fourier-Motzkin method,” IEICE Tech. Rep., CAS2001-65 or CST2001-18, Nov. 2001.

[8] T. Matsumoto, M. Osogami, and S. Moro, “How to obtain coefficients for a firing count vector expanded by T-invariants and particular solutions in P/T Petri nets,” Proc. of NOLTA'06, Bologna, Italy, pp.407-410, Sept.2006.