Home | Quick Search | Advanced Search | Bibliography submission | Bibliography submission using bibtex | Bibliography submission using bibtex file | Links | Help | Internal


TitleReachability Test in Petri Nets by Gröbner Bases
Author(s) Olga Caprotti, Alois Ferscha, Hoon Hong
TypeTechnical Report, Misc
AbstractIn 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.
KeywordsPetri Nets, Reachability Problem, Equality Problem, Canonical Algebraic Simplification, Knuth-Bendix Algorithm, Gröbner Bases Algorithm
Translation No
Refereed No
Organization Johannes Kepler University Linz
Institution RISC (Research Institute for Symbolic Computation)