Free-Choice Petri Nets without Frozen Tokens, and Bipolar Synchronization Systems

• Autorzy: Wehler J.
• Języki publikacji: EN

Abstrakty

EN

Bipolar synchronization systems (BP-systems) constitute a class of coloured Petri nets, well suited for modelling the control flow of discrete dynamical systems. Every BP-system has an underlying ordinary Petri net, a T-system. It further has a second ordinary net attached, a free-choice system. We prove that a BP-system is safe and live if the T-system and the free-choice system are safe and live and the free-choice system in addition has no frozen tokens. This result is the converse of a theorem of Genrich and Thiagarajan and proves an old conjecture. As a consequence we obtain two results about the existence of safe and live BP-systems with prescribed ordinary Petri nets. For the proof of these theorems we introduce the concept of a morphism between Petri nets as a means of comparing different Petri nets. We then apply the classical theory of free-choice systems.

Słowa kluczowe

EN

bipolar synchronization system; free-choice system; frozen token; Petri net morphism; structurally free of blocking

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2010
• Tom: Vol. 98, nr 2/3
• Strony: 283--320
• Opis fizyczny: Bibliogr. 14 poz., wykr.

Twórcy

autor

Wehler J.

• Ludwig-Maximilians-Universität, Fakultät f¨ur Mathematik, Informatik und Statistik, Theresienstrasse 39/I, D-80333 München, Germany,

Bibliografia

• [BD1990] Best, Eike; Desel, J¨org: Partial Order Behaviour and Structure of Petri Nets. Formal Aspects of Computing (1990), p. 123-138
• [Des1986] Desel, J¨org: A structural property of Free-choice Systems. Petri Net Newsletter 25, 1986
• [DE1995] Desel, Jörg, Esparza, Javier: Free Choice Petri Nets. Cambridge University Press, Cambridge 1995
• [ES1990] Esparza, Javier; Silva, Manuel: Circuits, Handles, Bridges and Nets. In: Rozenberg, Grzegorz (Ed.) Advances in Petri nets 1990. Lecture Notes in Computer Science, vol. 483, Springer, Berlin 1990, p. 210-242
• [GHM2003] Gaujal, Bruno; Haar, Stefan; Mairesse, Jean: Blocking a transition in a Free Choice net and what it tells about its throughput. Journal of Computer and System Sciences 66 (2003), p. 515-548
• [GL2005] Gruhn, Volker; Laue, Ralf: Einfache EPK-Semantik durch praxistaugliche Stilregeln. In: Nüttgens, Markus; Rump, Frank (Hrsg.): EPK 2005. Geschäftsprozessmanagement mit Ereignisgesteuerten Prozessketten. Proceedings, Hamburg 2005
• [GT1984] Genrich, H.J.; Thiagarajan, P.S.: A Theory of Bipolar Synchronization Schemes. Theoretical Computer Science 30 (1984), p. 241-318
• [Jen1992] Jensen, Kurt: Coloured Petri nets. Basic concepts, analysis methods and practical use. Vol. 1. Springer, Berlin et al. 1992
• [LSW1998] Langner, Peter; Schneider, Christoph;Wehler, Joachim: Petri Net based Certification of Event-driven Process Chains. In: Desel, J¨org; Silva, Manuel (Eds.): Application and Theory of Petri Nets 1998. Lecture notes in Computer science, vol. 1420. Springer, Berlin et al. 1998
• [MA2006] Mendling, Jan; van der Aalst, Wil: Towards EPC Semantics based on State and Context. In: Nüttgens, Markus; Rump, Frank: EPK 2006. Geschäftsprozessmanagement mit Ereignisgesteuerten Prozessketten. 5., Workshop der Gesellschaft für Informatik,Wien, 2006
• [Sch1994] Scheer, August-Wilhelm: Business Process Engineering. Reference Models for Industrial Enterprises. Springer, Berlin et al. 1994
• [TV1984] Thiagarajan, P.S.; Voss, Klaus: A Fresh Look at Free Choice Nets. Information and Control 62 (1984), p. 85-113
• [Weh2006] Wehler, Joachim: Morphisms of Coloured Petri Nets, arXiv, cs.SE/0608038, 2006
• [Weh2007] Wehler, Joachim: Boolean and free-choice semantics of Event-driven Process Chains. EPK 2007. In: Nüttgens, Markus; Rump, Frank, Gadatsch, Andreas (Eds.): 6. GI-Workshop EPK 2007: Geschäftsprozessmanagementmit Ereignisgesteuerten Prozessketten. St.Augustin, 2007.