Controlling Petri Net Behavior using Priorities for Transitions

• Autorzy: Lomazova I. A. , Popova-Zeugmann L.

Identyfikatory

DOI

10.3233/FI-2016-1306

• Języki publikacji: EN

Abstrakty

EN

In this paper we examine how it is possible to control Petri net behavior with the help of transition priorities. Controlling here means forcing a process to behave in a stable way by ascribing priorities to transitions and hence transforming a classic Petri net into a Priority Petri net. For Petri net models stability is often ensured by liveness and boundedness. These properties are crucial in many application areas, e.g. workflow modeling, embedded systems design, and bioinformatics. In this paper we study the problem of transforming a given live, but unbounded Petri net into a live and bounded one by adding priority constraints. We specify necessary conditions for the solvability of this problem and present an algorithm for ascribing priorities to net transitions in such a way that the resulting net becomes bounded while staying live.

Słowa kluczowe

EN

Petri nets; bioinformatics; stability theory; workflow; system design

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2016
• Tom: Vol. 143, nr 1/2
• Strony: 101--112
• Opis fizyczny: Bibliogr. 16 poz., rys.

Twórcy

autor

Lomazova I. A.

• National Research University Higher School of Economics (HSE), Moscow, 101000, Russia

autor

Popova-Zeugmann L.

• Humboldt-Universität zu Berlin, Unter den Linden 6, 10099 Berlin, Germany

Bibliografia

• [1] W.M.P. van der Aalst, K.M. van Hee, A.H.M. Hofstede, N. Sidorova, H.M.W. Verbeek, M. Voorhoeve, M.T. Wynn: Soundness of Workflow Nets: Classification, Decidability, and Analysis. Formal Aspects of Computing, Vol. 23, No 3, pages 333–363, Springer, 2011.
• [2] V.A. Bashkin, I.A. Lomazova: Decidability of k-Soundness for Workflow Nets with an Unbounded Resource. Transactions on Petri Nets and Other Models of Concurrency IX, Lecture Notes in Computer Science, Vol. 8910, pages 1–78. Springer, 2014.
• [3] E. Best, M. Koutny: Petri net semantics of priority systems. Theoretical Computer Science, Vol. 96, No. 1, pages 175–215, 1992.
• [4] E. Best, R. Devillers: Characterization of the State Spaces of Live and Bounded Marked Graph Petri Nets. In: Language and Automata Theory and Applications, Lecture Notes in Computer Science, Vol. 8370, pages 161-172, 2014.
• [5] J. Desel: On Cyclic Behaviour of Unbounded Petri Nets. In: Application of Concurrency to System Design (ACSD) . 13th International Conference on Application of Concurrency to System Design, pages 110–119. IEEE, 2013.
• [6] J. Desel: Schwach beschränkte Petrinetze. 12ter Workshop Algorithmen und Werkzeuge für Petrinetze, 29. - 30. September 2005.
• [7] K. van Hee, O. Oanea, A. Serebrenik, N. Sidorova, M. Voorhoeve, I.A. Lomazova: Checking Properties of Adaptive Workflow Nets. Fundamenta Informaticae, Vol. 79, No. 3, pages 347–362, 2007.
• [8] M. Heiner: Biochemically Interpreted Petri Nets - Two Open Problems. Talk, Seminaire MeFoSyLoMa (Formal Methods for Hardware and Software Systems), Universit Paris 13, June 2007.
• [9] M Heiner: Time Petri nets for modelling and analysis of biochemical networks - on the influence of time. Talk, MaReBio, Marseille, November 2008.
• [10] C. Liu, Cong, A. Kondratyev, Y. Watanabe, J. Desel, A. Sangiovanni-Vincentelli: Schedulability analysis of Petri nets based on structural properties. Fundamenta Informaticae, Vol. 86, No 3, pages 325–341, 2008.
• [11] I. A. Lomazova: Interacting Workflow Nets for Workflow Process Re-Engineering. Fundamenta Informaticae, Vol. 101, No 1-2, pages 59–70, 2010.
• [12] I.A. Lomazova, I.V. Romanov: Analyzing Compatibility of Services via Resource Conformance. Fundamenta Informaticae, Vol. 128, No. 1, pages 129–141, 2013.
• [13] T. Murata: Petri Nets: Properties, Analysis and Applications. An invited survey paper. Proceedings of the IEEE, Vol.77, No.4 pp.541–580, April, 1989.
• [14] N. Sidorova, C. Stahl: Soundness for Resource-Contrained Workflow Nets is Decidable. IEEE Transactions on Systems, Man, and Cybernetics, Vol. 43, No. 3, pages 724–72, 2013.
• [15] L. Popova-Zeugmann: Time and Petri Nets. Springer-Verlag, Springer Heidelberg New York Dordrecht London, 2013.
• [16] N. Ridder, K. Lautenbach: Liveness in bounded Petri nets which are covered by T-invariants. In: R. Valette (Ed.), Application and Theory of Petri Nets, Lecture Notes in Computer Science, Vol. 815, pages 358–378, Springer, 1994.