We define 2 operators on relations over natural numbers such that they generalize the operators '+' and '*' and show that the membership and emptiness problem of relations constructed from finite relations with these operators and ∪ is decidable. This generalizes Presburger arithmetics and allows to decide the reachability problem for those Petri nets where inhibitor arcs occur only in some restricted way. Especially the reachability problem is decidable for Petri nets with only one inhibitor arc, which solves an open problem in [KLM89] . Furthermore we describe the corresponding automaton having a decidable emptiness problem.
The reachability problem of Petri nets with one inhibitor arc is studied in REF and shown to be decidable.
Reachability in Petri Nets with Inhibitor Arcs
Electr. Notes Theor. Comput. Sci.
Computer Science Mathematics