An Application of Grobner Basis Approach to Petri Net Problems

Tadashi MATSUMOTO  Maki TAKATA  Seiichiro MORO  

Publication
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences   Vol.E86-A   No.11   pp.2791-2796
Publication Date: 2003/11/01
Online ISSN: 
DOI: 
Print ISSN: 0916-8508
Type of Manuscript: Special Section LETTER (Special Section on Concurrent System Technology)
Category: 
Keyword: 
integer programming,  Grobner basis,  Buchberger algorithm,  algebraic geometry,  P/T Petri net problems,  symbolic computation systems,  

Full Text: PDF>>
Buy this Article




Summary: 
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.