Free-choice Nets with Home Clusters are Lucent

• Autorzy: van der Aalst Wil M. P.

Identyfikatory

DOI

10.3233/FI-2021-2059

• Języki publikacji: EN

Abstrakty

EN

A marked Petri net is lucent if there are no two different reachable markings enabling the same set of transitions, i.e., states are fully characterized by the transitions they enable. Characterizing the class of systems that are lucent is a foundational and also challenging question. However, little research has been done on the topic. In this paper, it is shown that all free-choice nets having a home cluster are lucent. These nets have a so-called home marking such that it is always possible to reach this marking again. Such a home marking can serve as a regeneration point or as an end-point. The result is highly relevant because in many applications, we want the system to be lucent and many “well-behaved” process models fall into the class identified in this paper. Unlike previous work, we do not require the marked Petri net to be live and strongly-connected. Most of the analysis techniques for free-choice nets are tailored towards well-formed nets. The approach presented in this paper provides a novel perspective enabling new analysis techniques for free-choice nets that do not need to be well-formed. Therefore, we can also model systems and processes that are terminating and/or have an initialization phase.

Słowa kluczowe

EN

Petri nets; free-choice nets; lucent process models

• Wydawca: Polskie Towarzystwo Matematyczne
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2021
• Tom: Vol. 181, nr 4
• Strony: 273--302
• Opis fizyczny: Bibliogr. 20 poz., rys., tab.

Twórcy

autor

van der Aalst Wil M. P.

• Process and Data Science (PADS), RWTH Aachen University, Germany

Bibliografia

• [1] Reisig W, Rozenberg G (eds.). Lectures on Petri Nets I: Basic Models, volume 1491 of Lecture Notes in Computer Science. Springer-Verlag, Berlin, 1998. doi:10.1007/3-540-65306-6.
• [2] Best E, Wimmel H. Structure Theory of Petri Nets. In: Jensen K, van der Aalst W, Balbo G, Koutny M, Wolf K (eds.), Transactions on Petri Nets and Other Models of Concurrency (ToPNoC VII), volume 7480 of Lecture Notes in Computer Science. Springer-Verlag, Berlin, 2013 pp. 162-224. doi:10.1007/978-3-642-38143-0_5.
• [3] Murata T. Petri Nets: Properties, Analysis and Applications. Proceedings of the IEEE, 1989. 77(4):541-580. doi:10.1109/5.24143.
• [4] van der Aalst W, van Hee K, ter Hofstede A, Sidorova N, Verbeek H, Voorhoeve M, Wynn M. Soundness of Workflow Nets: Classification, Decidability, and Analysis. Formal Aspects of Computing, 2011. 23(3):333-363. doi:10.1007/s00165-010-0161-4.
• [5] van der Aalst W. Markings in Perpetual Free-Choice Nets Are Fully Characterized by Their Enabled Transitions. In: Khomenko V, Roux O (eds.), Applications and Theory of Petri Nets 2018, volume 10877 of Lecture Notes in Computer Science. Springer-Verlag, Berlin, 2018 pp. 315-336. doi:10.1007/978-3-319-91268-4_16.
• [6] van der Aalst W. Lucent Process Models and Translucent Event Logs. Fundamenta Informaticae, 2019. 169(1-2):151-177. doi:10.3233/FI-2019-1842.
• [7] van der Aalst W. Process Mining: Data Science in Action. Springer-Verlag, Berlin, 2016. doi:10.1007/978-3-662-49851-4.
• [8] Desel J, Esparza J. Free Choice Petri Nets, volume 40 of Cambridge Tracts in Theoretical Computer Science. Cambridge University Press, Cambridge, UK, 1995. doi:10.1017/CBO9780511526558.
• [9] Best E. Structure Theory of Petri Nets: the Free Choice Hiatus. In: Brauer W, Reisig W, Rozenberg G (eds.), Advances in Petri Nets 1986 Part I: Petri Nets, central models and their properties, volume 254 of Lecture Notes in Computer Science. Springer-Verlag, Berlin, 1987 pp. 168-206. doi:10.1007/978-3-540-47919-2_8.
• [10] van der Aalst W. The Application of Petri Nets to Workflow Management. The Journal of Circuits, Systems and Computers, 1998. 8(1):21-66. doi:10.1142/S0218126698000043.
• [11] van der Aalst W, Stahl C. Modeling Business Processes: A Petri Net Oriented Approach. MIT Press, Cambridge, MA, 2011. doi:10.7551/mitpress/8811.003.0001.
• [12] Reisig W. Understanding Petri Nets: Modeling Techniques, Analysis, Methods, Case Studies. Springer-Verlag, Berlin, 2013. doi:10.1007/978-3-642-33278-4.
• [13] Reisig W, Rozenberg G (eds.). Lectures on Petri Nets II: Applications, volume 1492 of Lecture Notes in Computer Science. Springer-Verlag, Berlin, 1998. doi:10.1007/3-540-65307-4.
• [14] Best E, Desel J, Esparza J. Traps Characterize Home States in Free-Choice Systems. Theoretical Computer Science, 1992. 101:161-176. doi:10.1016/0304-3975(92)90048-K.
• [15] Esparza J. Reachability in Live and Safe Free-Choice Petri Nets is NP-Complete. Theoretical Computer Science, 1998. 198(1-2):211-224. doi:10.1016/S0304-3975(97)00235-1.
• [16] Thiagarajan P, Voss K. A Fresh Look at Free Choice Nets. Information and Control, 1984. 61(2):85-113. doi:10.1016/S0019-9958(84)80052-2.
• [17] Wehler J. Free-Choice Petri Nets without Frozen Tokens, and Bipolar Synchronization Systems. Fundamenta Informaticae, 2010. 98(2-3):283-320. doi:10.3233/FI-2010-228.
• [18] Gaujal B, Haar S, Mairesse J. Blocking a Transition in a Free Choice Net and What it Tells About its Throughput. Journal of Computer and System Science, 2003. 66(3):515-548. doi:10.1016/S0022-0000(03)00039-4.
• [19] Wehler J. Simplified Proof of the Blocking Theorem for Free-Choice Petri Nets. Journal of Computer and System Science, 2010. 76(7):532-537. doi:10.1016/j.jcss.2009.10.001.
• [20] van der Aalst W. Reduction Using Induced Subnets to Systematically Prove Properties for Free-Choice Nets. In: Buchs D, Carmona J (eds.), Applications and Theory of Petri Nets 2021, volume 12734 of Lecture Notes in Computer Science. Springer-Verlag, Berlin, 2021 pp. 208-229. doi:10.1007/978- 3-030-76983-3_11.