Article ID Journal Published Year Pages File Type
426794 Information and Computation 2013 11 Pages PDF
Abstract

The notion of persistency, based on the rule “no action can disable another one” is one of the classical notions in concurrency theory. In this paper, we deal with arbitrary place/transition nets, but concentrate on their persistent computations. It leads to an interesting decision problem: Is a given marking reachable with a persistent run? In order to study the persistent-reachability problem we define a class of nets, called nonviolence nets. We show that inhibitor nets can be simulated by the nonviolence nets (and vice versa), thus the latter are computationally Turing powerful and reachability and coverability problems are undecidable in the class of the nonviolence nets.

Related Topics
Physical Sciences and Engineering Computer Science Computational Theory and Mathematics
Authors
, , ,