Finding an non-negative integer solution x∈ Znx1 for Ax = b (A∈Zmxn, b∈Zmxl) 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 Groebner 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 paper, two kinds of examples are given to show how Groebner basis approach is applied to reachability problems in Petri nets.
展开▼
