|Discrete Mathematics and Optimization Seminar
University of Tuebingen
Monday March 14th at 4.30pm
Title. Reachability in Petri Nets with Inhibitor Arcs.
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 $\cup$ 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.