Levels of Persistency in Place/Transition Nets

• Autorzy: Barylska K. , Ochmański E.
• Języki publikacji: EN

Abstrakty

EN

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.

Słowa kluczowe

EN

place/transition Petri net

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2009
• Tom: Vol. 93, nr 1-3
• Strony: 33--43
• Opis fizyczny: Bibliogr. 13 poz., wykr.

Twórcy

autor

Barylska K.

autor

Ochmański E.

• Faculty of Mathematics and Computer Science, Nicolaus Copernicus University, Chopina 12/18, 87-100 Toruń, Poland,

Bibliografia

• [1] E. Best, P. Darondeau: Decomposition Theorems for Bounded Persistent Petri Nets, Proc. of Petri Nets 2008, LNCS 5062, pp. 33-51, Springer 2008.
• [2] J. Desel, W. Reisig: Place/Transition Petri Nets, Lectures on Petri Nets, LNCS 1491, pp. 122-173. Springer, 1998.
• [3] L. E. Dickson: Finiteness of the odd perfect and primitive abundant numbers with n distinct prime factors, Amer. Journal Math. 35, vol. I, pp. 413-422, 1913.
• [4] 4. S. Eilenberg, M.P. Schtzenberger: Rational sets in commutative monoids, Journal of Algebra 13, pp. 173-191, 1969.
• [5] S. Ginsburg, E. Spanier: Bounded ALGOL-like Languages. Trans. Amer. Math. Soc. 113, pp. 333-368, 1964.
• [6] J. Grabowski: The Decidability of Persistence for Vector Addition Systems, Information Processing Letters 11(1), pp. 20-23, 1980.
• [7] M.H.T. Hack: Decidability Questions for Petri Nets, Ph. D. Thesis, M.I.T. 1976.
• [8] R.M. Karp, R.E. Miller: Parallel program schemata. Journal of Computer and System Sciences 3, pp. 147-195, 1969.
• [9] S.R. Kosaraju: Decidability of Reachability in Vector Addition Systems. Proceedings of the 14th Annual ACM Symposium on Theory of Computing, pp. 267-281, 1982.
• [10] L.H. Landweber, E.L. Robertson: Properties of conflict-free and persistent Petri nets, Journal of ACM 25, pp. 352-364, 1978.
• [11] E. Mayr: Persistence of Vector Replacement Systems is Decidable, Acta Informatica 15, pp. 309-318, 1981.
• [12] E.W. Mayr: An Algorithm for the General Petri Net Reachability Problem. Proceedings of the 13th Annual ACM Symposium on Theory of Computing, pp. 238-246, 1981.
• [13] R. Valk, M. Jantzen: The Residue of Vector Sets with Applications to Decidability Problems in Petri Nets, Acta Informatica 21, pp. 643-674, 1985.