Lucent Process Models and Translucent Event Logs

• Autorzy: van der Aalst, Wil M. P.
• Języki publikacji: EN

Abstrakty

EN

A process model is lucent if no two reachable states are enabling the same set of activities. An event log is translucent if each event carries information about the set of activities enabled when the event occurred (normally one only sees the activity performed). Both lucency and translucency focus on the set of enabled activities and are therefore related. Surprisingly, these notions have not been investigated before. This paper aims to (1) characterize process models that are lucent, (2) provide a discovery approach to learn process models from translucent event logs, and (3) relate lucency and translucency. Lucency is defined both in terms of automata and Petri nets. 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. We will also provide a novel process discovery technique starting from a translucent event log. It turns out that information about the set of activities is extremely valuable for process discovery. We will provide sufficient conditions to ensure that the discovered model is lucent and show that a translucent event log sampled from a lucent process model can be used to rediscover the original model. We anticipate new analysis techniques exploiting lucency. Moreover, as shown in this paper, translucent event logs provide valuable information that can be exploited by a new breed to process mining techniques.

Słowa kluczowe

EN

process mining; Petri nets; lucent process models; translucent event logs

• Czasopismo: Fundamenta Informaticae
• Rocznik: 2019
• Tom: Vol. 169, nr 1-2
• Strony: 151--177
• Opis fizyczny: Bibliogr. 32 poz., rys., tab.

Twórcy

autor

van der Aalst, Wil M. P.

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

Bibliografia

• [1] 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.
• [2] van der Aalst W, Stahl C. Modeling Business Processes: A Petri Net Oriented Approach. MIT Press, Cambridge, MA, 2011. URL https://www.jstor.org/stable/j.ctt5vjqff.
• [3] Murata T. Petri Nets: Properties, Analysis and Applications. Proceedings of the IEEE, 1989. 77(4):541-580. doi:10.1109/5.24143.
• [4] Reisig W. Petri Nets: Modeling Techniques, Analysis, Methods, Case Studies. Springer-Verlag, Berlin, 2013. doi:10.1007/978-3-642-33278-4.
• [5] 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.
• [6] 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.
• [7] 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.
• [8] 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.
• [9] Desel J, Esparza J. Free Choice Petri Nets, volume 40 of Cambridge Tracts in Theoretical Computer Science. Cambridge University Press, Cambridge, UK, 1995. ISBN:0-521-46519-2.
• [10] 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.
• [11] Esparza J. Reachability in Live and Safe Free-Choice Petri Nets is NP-Complete. Theoretical Computer Science, 1998. 198(1-2):211-224. URL https://doi.org/10.1016/S0304-3975(97)00235-1.
• [12] Thiagarajan P, Voss K. A fresh look at free choice nets. Information and Control, 1984. 61(2):85-113. URL https://doi.org/10.1016/S0019-9958(84)80052-2.
• [13] 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.
• [14] 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. URL https://doi.org/10.1016/S0022-0000(03)00039-4.
• [15] Wehler J. Simplified Proof of the Blocking Theorem for Free-Choice Petri Nets. Journal of Computer and System Science, 2010. 76(7):532-537. URL https://doi.org/10.1016/j.jcss.2009.10.001.
• [16] van der Aalst W. Process Mining: Data Science in Action. Springer-Verlag, Berlin, 2016. doi:10.1007/978-3-662-49851-4.
• [17] van der Aalst W, Rubin V, Verbeek H, van Dongen B, Kindler E, Günther C. Process Mining: A Two-Step Approach to Balance Between Underfitting and Overfitting. Software and Systems Modeling, 2010. 9(1):87-111. doi:10.1007/s10270-008-0106-z.
• [18] van der Aalst W, Weijters A, Maruster L. Workflow Mining: Discovering Process Models from Event Logs. IEEE Transactions on Knowledge and Data Engineering, 2004. 16(9):1128-1142. doi:10.1109/TKDE.2004.47.
• [19] Bergenthum R, Desel J, Lorenz R, Mauser S. Process Mining Based on Regions of Languages. In: Alonso G, Dadam P, Rosemann M (eds.), International Conference on Business Process Management (BPM 2007), volume 4714 of Lecture Notes in Computer Science. Springer-Verlag, Berlin, 2007 pp. 375-383. doi:10.1007/978-3-540-75183-0_27.
• [20] Leemans S, Fahland D, van der Aalst W. Discovering Block-Structured Process Models from Event Logs Containing Infrequent Behaviour. In: Lohmann N, Song M, Wohed P (eds.), Business Process Management Workshops, International Workshop on Business Process Intelligence (BPI 2013), volume 171 of Lecture Notes in Business Information Processing. Springer-Verlag, Berlin, 2014 pp. 66-78. doi:10.1007/978-3-319-06257-0_6.
• [21] Leemans S, Fahland D, van der Aalst W. Scalable Process Discovery and Conformance Checking. Software and Systems Modeling, 2018. 17(2):599-631. doi:10.1007/s10270-016-0545-x.
• [22] Solé M, Carmona J. Process Mining from a Basis of State Regions. In: Applications and Theory of Petri Nets (Petri Nets 2010), volume 6128 of Lecture Notes in Computer Science. Springer-Verlag, Berlin, 2010 pp. 226-245. doi:10.1007/978-3-642-13675-7_14.
• [23] van der Werf J, van Dongen B, Hurkens C, Serebrenik A. Process Discovery using Integer Linear Programming. Fundamenta Informaticae, 2010. 94:387-412. doi:10.3233/FI-2009-136.
• [24] van der Aalst W, Adriansyah A, van Dongen B. Replaying History on Process Models for Conformance Checking and Performance Analysis. WIREs Data Mining and Knowledge Discovery, 2012. 2(2):182-192. URL https://doi.org/10.1002/widm.1045.
• [25] Carmona J, van Dongen B, Solti A, Weidlich M. Conformance Checking: Relating Processes and Models. Springer-Verlag, Berlin, 2018. doi:10.1007/978-3-319-99414-7.
• [26] Ehrenfeucht A, Rozenberg G. Partial (Set) 2-Structures - Part 1 and Part 2. Acta Informatica, 1989. 27(4):315-368.
• [27] Cortadella J, Kishinevsky M, Lavagno L, Yakovlev A. Deriving Petri Nets from Finite Transition Systems. IEEE Transactions on Computers, 1998. 47(8):859-882. doi:10.1109/12.707587.
• [28] Carmona J. The Label Splitting Problem. In: Jensen K, van der Aalst W, Marsan MA, Franceschinis G, Kleijn J, Kristensen L (eds.), Transactions on Petri Nets and Other Models of Concurrency (ToPNoC VI), volume 7400 of Lecture Notes in Computer Science. Springer-Verlag, Berlin, 2012 pp. 1-23. doi:10.1007/978-3-642-35179-2_1.
• [29] van der Aalst W. The Application of Petri Nets to Workflow Management. The Journal of Circuits, Systems and Computers, 1998. 8(1):21-66. URL https://doi.org/10.1142/S0218126698000043.
• [30] 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.
• [31] Genrich HJ, Thiagarajan PS. A Theory of Bipolar Synchronization Schemes. Theoretical Computer Science, 1984. 30(3):241-318. URL https://doi.org/10.1016/0304-3975(84)90137-3¿
• [32] Badouel E, Bernardinello L, Darondeau P. Petri Net Synthesis. Texts in Theoretical Computer Science. An EATCS Series. Springer-Verlag, Berlin, 2015. doi:10.1007/978-3-662-47967-4.

Uwagi

Opracowanie rekordu w ramach umowy 509/P-DUN/2018 ze środków MNiSW przeznaczonych na działalność upowszechniającą naukę (2019).

Identyfikatory

DOI

10.3233/FI-2019-1842