Search

In a persistent vector replacement system (VRS) or Petri net, an enabled transition can become disabled only by firing itself. Here, an algorithm is presented which allows to decide whether an arbitrary VRS is persistent of not, and if so, to construct a semilinera representation of the set of states reachable in the system.

Any decision procedure for the word problems for commutative semigroups and polynomial ideals inherently requires computational storage space growing exponentially with the size of the problem instrance to which the procedure is applied. This bound is achieved by a simple procedure for the semigroup problem.

In a persistent Petri net, an enabled transition can become disabled only by firing itself. Here, an algorithm is presented which constructs a semilinear representation of the set of states reachable in an arbitrary persistent Petri net.

If the reachability set of a Petri net (or, equivalently, vector addition system) is finite it can be effectively constructed. Furthermore, the finiteness is decidable. Thus, the containment and equality problem for finite reachability sets become solvable. We investigate the complexity of decision procedures for these problems and show by reducing a bounded version of Hilbert's Tenth Problem to the finite containment problem that these two problems are extremely hard, that, in fact, the complexity of each decision procedure exceeds any primitive recursive function infinitely often.