Reachability in Petri Nets with Inhibitor Arcs | Zendy

Klaus Reinhardt | Zendy

AI Assistant Blog Pricing

Home ZAIA Blog

Open Access

Reachability in Petri Nets with Inhibitor Arcs

Author(s) -

Klaus Reinhardt

Publication year - 2008

Publication title -

electronic notes in theoretical computer science

Language(s) - English

Resource type - Journals

SCImago Journal Rank - 0.242

H-Index - 60

ISSN - 1571-0661

DOI - 10.1016/j.entcs.2008.12.042

Subject(s) - decidability , reachability , petri net , reachability problem , mathematics , discrete mathematics , automaton , presburger arithmetic , combinatorics , computer science , theoretical computer science , algorithm

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 [H. Kleine Büning, T. Lettmann, and E. W. Mayr. Projections of vector addition system reachability sets are semilinear. Theoret. Comput. Sci., 64:343–350, 1989]. Furthermore we describe the corresponding automaton having a decidable emptiness problem

The content you want is available to Zendy users.

Already have an account? Click here to sign in.

Having issues? You can contact us here

Accelerating Research