Logo PTI Logo FedCSIS

Proceedings of the 16th Conference on Computer Science and Intelligence Systems

Annals of Computer Science and Information Systems, Volume 25

Using Free-Choice Nets for Process Mining and Business Process Management

DOI: http://dx.doi.org/10.15439/2021F002

Citation: Proceedings of the 16th Conference on Computer Science and Intelligence Systems, M. Ganzha, L. Maciaszek, M. Paprzycki, D. Ślęzak (eds). ACSIS, Vol. 25, pages 9–15 ()

Full text

Abstract. Free-choice nets, a subclass of Petri nets, have been studied for decades. They are interesting because they have many desirable properties normal Petri nets do not have and can be analyzed efficiently. Although the majority of process models used in practice are inherently free-choice, most users (even modeling experts) are not aware of free-choice net theory and associated analysis techniques. This paper discusses free-choice nets in the context of process mining and business process management. For example, state-of-the-art process discovery algorithms like the inductive miner produce process models that are free-choice. Also, hand-made process models using languages like BPMN tend to be free-choice because choice and synchronization are separated in different modeling elements. Therefore, we introduce basic notions and results for this important class of process models. Moreover, we also present new results for free-choice nets particularly relevant for process mining. For example, we elaborate on home clusters and lucency as closely-related and desirable correctness notions. We also discuss the limitations of free-choice nets in process mining and business process management, and suggest research directions to extend free-choice nets with non-local dependencies.

References

  1. W.M.P. van der Aalst. The Application of Petri Nets to Workflow Management. The Journal of Circuits, Systems and Computers, 8(1):21–66, 1998.
  2. W.M.P. van der Aalst. Process Mining: Data Science in Action. Springer-Verlag, Berlin, 2016.
  3. W.M.P. van der Aalst. Markings in Perpetual Free-Choice Nets Are Fully Characterized by Their Enabled Transitions. In V. Khomenko and O. Roux, editors, Applications and Theory of Petri Nets 2018, volume 10877 of Lecture Notes in Computer Science, pages 315–336. Springer-Verlag, Berlin, 2018.
  4. W.M.P. van der Aalst. A Practitioner’s Guide to Process Mining: Limitations of the Directly-Follows Graph. In International Conference on Enterprise Information Systems (Centeris 2019), volume 164 of Procedia Computer Science, pages 321–328. Elsevier, 2019.
  5. W.M.P. van der Aalst. Lucent Process Models and Translucent Event Logs. Fundamenta Informaticae, 169(1-2):151–177, 2019.
  6. W.M.P. van der Aalst. Free-Choice Nets With Home Clusters Are Lucent. Fundamenta Informaticae, 181(4):273–302, 2021.
  7. W.M.P. van der Aalst. Reduction Using Induced Subnets to Systematically Prove Properties for Free-Choice Nets. In D. Buchs and J. Carmona, editors, Applications and Theory of Petri Nets and Concurrency (PN 2021), volume 12734 of Lecture Notes in Computer Science, pages 208–229. Springer-Verlag, Berlin, 2021.
  8. W.M.P. van der Aalst and K.M. van Hee. Workflow Management: Models, Methods, and Systems. MIT Press, Cambridge, MA, 2002.
  9. W.M.P. van der Aalst, K.M. van Hee, A.H.M. ter Hofstede, N. Sidorova, H.M.W. Verbeek, M. Voorhoeve, and M.T. Wynn. Soundness of Workflow Nets: Classification, Decidability, and Analysis. Formal Aspects of Computing, 23(3):333–363, 2011.
  10. W.M.P. van der Aalst, R. De Masellis, C. Di Francescomarino, and C. Ghidini. Learning Hybrid Process Models From Events: Process Discovery Without Faking Confidence. In J. Carmona, G. Engels, and A. Kumar, editors, International Conference on Business Process Management (BPM 2017), volume 10445 of Lecture Notes in Computer Science, pages 59–76. Springer-Verlag, Berlin, 2017.
  11. W.M.P. van der Aalst and C. Stahl. Modeling Business Processes: A Petri Net Oriented Approach. MIT Press, Cambridge, MA, 2011.
  12. W.M.P. van der Aalst, A.J.M.M. Weijters, and L. Maruster. Workflow Mining: Discovering Process Models from Event Logs. IEEE Transactions on Knowledge and Data Engineering, 16(9):1128–1142, 2004.
  13. A. Augusto, R. Conforti, M. Marlon, M. La Rosa, and A. Polyvyanyy. Split Miner: Automated Discovery of Accurate and Simple Business Process Models from Event Logs. Knowledge Information Systems, 59(2):251–284, May 2019.
  14. E. Best, J. Desel, and J. Esparza. Traps Characterize Home States in Free-Choice Systems. Theoretical Computer Science, 101:161–176, 1992.
  15. E. Best and H. Wimmel. Structure Theory of Petri Nets. In K. Jensen, W.M.P. van der Aalst, G. Balbo, M. Koutny, and K. Wolf, editors, Transactions on Petri Nets and Other Models of Concurrency (ToPNoC VII), volume 7480 of Lecture Notes in Computer Science, pages 162–224. Springer-Verlag, Berlin, 2013.
  16. J. Carmona, B. van Dongen, A. Solti, and M. Weidlich. Conformance Checking: Relating Processes and Models. Springer-Verlag, Berlin, 2018.
  17. J. Desel and J. Esparza. Free Choice Petri Nets, volume 40 of Cambridge Tracts in Theoretical Computer Science. Cambridge University Press, Cambridge, UK, 1995.
  18. C.A. Ellis and G.J. Nutt. Computer Science and Office Information Systems. Xerox, Palo Alto Research Center, 1979.
  19. J. Esparza. Reachability in Live and Safe Free-Choice Petri Nets is NP-Complete. Theoretical Computer Science, 198(1-2):211–224, 1998.
  20. S.J.J. Leemans, D. Fahland, and W.M.P. van der Aalst. Discovering Block-structured Process Models from Event Logs: A Constructive Approach. In J.M. Colom and J. Desel, editors, Applications and Theory of Petri Nets 2013, volume 7927 of Lecture Notes in Computer Science, pages 311–329. Springer-Verlag, Berlin, 2013.
  21. S.J.J. Leemans, D. Fahland, and W.M.P. van der Aalst. Discovering Block-Structured Process Models from Event Logs Containing Infrequent Behaviour. In N. Lohmann, M. Song, and P. Wohed, editors, Business Process Management Workshops, International Workshop on Business Process Intelligence (BPI 2013), volume 171 of Lecture Notes in Business Information Processing, pages 66–78. Springer-Verlag, Berlin, 2014.
  22. S.J.J. Leemans, D. Fahland, and W.M.P. van der Aalst. Scalable Process Discovery and Conformance Checking. Software and Systems Modeling, 17(2):599–631, 2018.
  23. L. Mannel and W.M.P. van der Aalst. Finding Complex Process-Structures by Exploiting the Token-Game. In S. Donatelli and S. Haar, editors, Applications and Theory of Petri Nets 2019, volume 11522 of Lecture Notes in Computer Science, pages 258–278. Springer-Verlag, Berlin, 2019.
  24. M. Zur Muehlen and J. Recker. How Much Language Is Enough? Theoretical and Practical Use of the Business Process Modeling Notation. In Z. Bellahsene and M. Léonard, editors, Proceedings of the 20th International Conference on Advanced Information Systems Engineering (CAiSE’08), volume 5074 of Lecture Notes in Computer Science, pages 465–479. Springer-Verlag, Berlin, 2008.
  25. T. Murata. Petri Nets: Properties, Analysis and Applications. Proceedings of the IEEE, 77(4):541–580, April 1989.
  26. OMG. Business Process Model and Notation (BPMN). Object Management Group, formal/2011-01-03, 2011.
  27. C. Ouyang, M. Dumas, A.H.M. ter Hofstede, and W.M.P. van der Aalst. Pattern-Based Translation of BPMN Process Models to BPEL Web Services. International Journal of Web Services Research, 5(1):42–62, 2007.
  28. H.A. Reijers, I.T.P. Vanderfeesten, and W.M.P. van der Aalst. The Effectiveness of Workflow Management Systems: A Longitudinal Study. International Journal of Information Management, 36(1):126–141, 2016.
  29. W. Reisig. Petri Nets: Modeling Techniques, Analysis, Methods, Case Studies. Springer-Verlag, Berlin, 2013.
  30. A. Rozinat and W.M.P. van der Aalst. Conformance Checking of Processes Based on Monitoring Real Behavior. Information Systems, 33(1):64–95, 2008.
  31. F.W. Taylor. The Principles of Scientific Management. Harper and Bothers Publishers, New York, 1919.
  32. P.S. Thiagarajan and K. Voss. A Fresh Look at Free Choice Nets. Information and Control, 61(2):85–113, 1984.
  33. S.J. van Zelst, B.F. van Dongen, W.M.P. van der Aalst, and H.M.W Verbeek. Discovering Workflow Nets Using Integer Linear Programming. Computing, 100(5):529–556, 2018.
  34. M.D. Zisman. Representation, Specification and Automation of Office Procedures. PhD thesis, University of Pennsylvania, Warton School of Business, 1977.