For Full-Text PDF, please login, if you are a member of IEICE,|
or go to Pay Per View on menu list, if you are a nonmember of IEICE.
An Application of Grobner Basis Approach to Petri Net Problems
Tadashi MATSUMOTO Maki TAKATA Seiichiro MORO
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences
Publication Date: 2003/11/01
Print ISSN: 0916-8508
Type of Manuscript: Special Section LETTER (Special Section on Concurrent System Technology)
integer programming, Grobner basis, Buchberger algorithm, algebraic geometry, P/T Petri net problems, symbolic computation systems,
Full Text: PDF>>
Finding a nonnegative integer solution x for Ax = b (A Zmn, b Zm1) in Petri nets is NP-complete. Being NP-complete, even algorithms with theoretically bad worst case and with average complexity can be useful for a special class of problems, hence deserve investigation. Then a Grobner basis approach to integer programming problems was proposed in 1991 and some symbolic computation systems became to have useful tools for ideals, varieties, and algorithms for algebraic geometry. In this letter, Grobner basis approach is applied to three typical problems with respect to state equation in P/T Petri nets. In other words, after Grobner bases are derived by the tool Maple 7, we consider how to derive the T-invariants and particular solutions of the Petri nets by using them in this letter.