Levels of Persistency in Place/Transition Nets

Issue title: Concurrency Specification and Programming (CS&P)

Article type: Research Article

Authors: Barylska, Kamila | Ochma´nski, Edward

Affiliations: Faculty of Mathematics and Computer Science, Nicolaus Copernicus University, Toruń, Poland. [email protected] | Faculty of Mathematics and Computer Science, Nicolaus Copernicus University, Toruń, Poland and Institute of Computer Science, Polish Academy of Sciences, Warszawa, Poland. [email protected]

Note: [] Address for correspondence: Nicolaus Copernicus University, Chopina 12/18, 87-100 Toruń, Poland

Abstract: The notion of persistency, based on the rule "no action can disable another one" is one of the classical notions in concurrency theory. We propose two ways of generalization of this notion: the first is "no action can kill another one" and the second "no action can kill another enabled one". We study the three notions in the context of place/transition nets, the fundamental class of Petri nets. We prove that the three classes of persistency form an increased strict hierarchy. The final section of the paper deals with decision problems about persistency. We show that the set reachability problem is decidable for rational convex sets, and using this result we prove that all kinds of persistency are decidable in the class place/transition nets.

DOI: 10.3233/FI-2009-0086

Journal: Fundamenta Informaticae, vol. 93, no. 1-3, pp. 33-43, 2009