Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
426794 | Information and Computation | 2013 | 11 Pages |
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
Kamila Barylska, Łukasz Mikulski, Edward Ochmanski,