|Title||Reachability Test in Petri Nets by Gröbner Bases|
|Author(s)|| Olga Caprotti, Alois Ferscha, Hoon Hong|
|Type||Technical Report, Misc|
|Abstract||In this paper we describe a decision procedure for the reachability|
problem in the class of Petri Nets that can be represented as a commutative semigroup with the set of places as generators, and the transition firing rules notated as polynomials. Given two markings represented as power products, and a Petri Net represented as a set of polynomials, reachability can be interpreted as congruence modulo a polynomial ideal. The Gröbner Bases algorithm is reviewed and then used as canonical simplifier for this equivalence.
|Keywords||Petri Nets, Reachability Problem, Equality Problem, Canonical Algebraic Simplification, Knuth-Bendix Algorithm, Gröbner Bases Algorithm|
Johannes Kepler University Linz|
RISC (Research Institute for Symbolic Computation)|