SpringerLink
Log in

Aligning Event Logs to Resource-Constrained \(\nu \)-Petri Nets

  • Conference paper
  • First Online:
Application and Theory of Petri Nets and Concurrency (PETRI NETS 2022)

Part of the book series: Lecture Notes in Computer Science ((LNCS,volume 13288))

Abstract

Systems with shared resources can be modeled and analyzed using high-level Petri nets in a natural way. Choosing a model type suitable for the use in conformance checking introduces challenges related to constraints the model should put on resource types and resource instances. In this paper, we propose a model for systems with shared resources based on resource-constrained Petri nets and \(\nu \)-Petri nets that can be used in the context of conformance checking. Our model allows for case and resource isolation, allowing for proper simulation of multiple cases involving shared resources.

With this minimal extension, we show that we can use existing state-of-the-art conformance checking techniques to compute alignments on complete event logs rather than on individual case instances. We show that previously undetected deviations caused by inter-case dependencies can now be exposed, providing valuable information regarding the exhaustive workflow in the process.

This work is done within the project “Certification of production process quality through Artificial Intelligence (CERTIF-AI)”, funded by NWO (project number: 17998).

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Subscribe and save

Springer+ Basic
EUR 32.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or Ebook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Chapter
USD 29.95
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
USD 64.99
Price excludes VAT (USA)
  • Available as EPUB and PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
USD 84.99
Price excludes VAT (USA)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free ship** worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Similar content being viewed by others

Notes

  1. 1.

    Adding a place p between two transitions \(t_a\) and \(t_b\) denotes a single arc from \(t_a\) to p and a single arc from p to \(t_b\).

References

  1. Adriansyah, A.: Aligning observed and modeled behavior. Ph.D. thesis, Mathematics and Computer Science (2014)

    Google Scholar 

  2. Alizadeh, M., Lu, X., Fahland, D., Zannone, N., van der Aalst, W.M.P.: Linking data and process perspectives for conformance analysis. Comput. Secur. 73, 172–193 (2018)

    Article  Google Scholar 

  3. Barkaoui, K., Petrucci, L.: Structural analysis of workflow nets with shared resources (1998)

    Google Scholar 

  4. Berti, A., van der Aalst, W.M.P.: A novel token-based replay technique to speed up conformance checking and process enhancement. Trans. Petri Nets Other Model. Concurr. 15, 1–26 (2021)

    MathSciNet  Google Scholar 

  5. Boltenhagen, M., Chatain, T., Carmona, J.: Optimized sat encoding of conformance checking artefacts. Computing 103(1), 29–50 (2021)

    Article  MathSciNet  Google Scholar 

  6. Carmona, J., van Dongen, B., Solti, A., Weidlich, M.: Conformance Checking. Springer, Heidelberg (2018)

    Book  Google Scholar 

  7. de Leoni, M., van der Aalst, W.M.P.: Aligning event logs and process models for multi-perspective conformance checking: an approach based on integer linear programming. In: Daniel, F., Wang, J., Weber, B. (eds.) BPM 2013. LNCS, vol. 8094, pp. 113–129. Springer, Heidelberg (2013). https://doi.org/10.1007/978-3-642-40176-3_10

    Chapter  Google Scholar 

  8. Decker, G., Weske, M.: Instance isolation analysis for service-oriented architectures. In: 2008 IEEE International Conference on Services Computing, vol. 1, pp. 249–256. IEEE (2008)

    Google Scholar 

  9. Fahland, D.: Describing behavior of processes with many-to-many interactions. In: Donatelli, S., Haar, S. (eds.) PETRI NETS 2019. LNCS, vol. 11522, pp. 3–24. Springer, Cham (2019). https://doi.org/10.1007/978-3-030-21571-2_1

    Chapter  Google Scholar 

  10. Ghilardi, S., Gianola, A., Montali, M., Rivkin, A.: Petri nets with parameterised data: modelling and verification (extended version). ar**v preprint ar**v:2006.06630 (2020)

  11. Kummer, O.: Undecidability in object-oriented Petri nets. In: Petri Net Newsletter. Citeseer (2000)

    Google Scholar 

  12. Lautenbach, K.: Liveness in Petri Nets. Bonn Interner Bericht ISF. Selbstverl, GMD (1975)

    Google Scholar 

  13. Lee, W.L.J., Verbeek, H.M.W., Munoz-Gama, J., van der Aalst, W.M.P., Sepúlveda, M.: Replay using recomposition: alignment-based conformance checking in the large. In: BPM (Demos) (2017)

    Google Scholar 

  14. Letia, I.A., Goron, A.: Model checking as support for inspecting compliance to rules in flexible processes. J. Vis. Lang. Comput. 28, 100–121 (2015)

    Article  Google Scholar 

  15. Mannhardt, F., De Leoni, M., Reijers, H.A., Van Der Aalst, W.M.P.: Balanced multi-perspective checking of process conformance. Computing 98(4), 407–437 (2016)

    Article  MathSciNet  Google Scholar 

  16. Mozafari Mehr, A.S., de Carvalho, R.M., van Dongen, B.: Detecting privacy, data and control-flow deviations in business processes. In: Nurcan, S., Korthaus, A. (eds.) CAiSE 2021. LNBIP, vol. 424, pp. 82–91. Springer, Cham (2021). https://doi.org/10.1007/978-3-030-79108-7_10

    Chapter  Google Scholar 

  17. Montali, M., Rivkin, A.: Model checking Petri nets with names using data-centric dynamic systems. Formal Aspects Comput. 28(4), 615–641 (2016)

    Article  MathSciNet  Google Scholar 

  18. Montali, M., Rivkin, A.: DB-Nets: on the marriage of colored Petri nets and relational databases. In: Koutny, M., Kleijn, J., Penczek, W. (eds.) Transactions on Petri Nets and Other Models of Concurrency XII. LNCS, vol. 10470, pp. 91–118. Springer, Heidelberg (2017). https://doi.org/10.1007/978-3-662-55862-1_5

    Chapter  Google Scholar 

  19. Murata, T.: Petri nets: properties, analysis and applications. Proc. IEEE 77(4), 541–580 (1989)

    Article  Google Scholar 

  20. Nielsen, M., Plotkin, G., Winskel, G.: Petri nets, event structures and domains. In: Kahn, G. (ed.) Semantics of Concurrent Computation. LNCS, vol. 70, pp. 266–284. Springer, Heidelberg (1979). https://doi.org/10.1007/BFb0022474

    Chapter  Google Scholar 

  21. Peterson, J.L.: Petri Net Theory and the Modeling of Systems. Prentice Hall PTR (1981)

    Google Scholar 

  22. Rosa-Velardo, F., de Frutos-Escrig, D.: Decision problems for Petri nets with names. ar**v preprint ar**v:1011.3964 (2010)

  23. Rosa-Velardo, F., de Frutos-Escrig, D., Marroquín-Alonso, O.: On the expressiveness of mobile synchronizing Petri nets. Electron. Notes Theor. Comput. Sci. 180(1), 77–94 (2007)

    Article  Google Scholar 

  24. Rozinat, A., Van der Aalst, W.M.P.: Conformance checking of processes based on monitoring real behavior. Inf. Syst. 33(1), 64–95 (2008)

    Article  Google Scholar 

  25. Taghiabadi, E.R., Gromov, V., Fahland, D., van der Aalst, W.M.P.: Compliance checking of data-aware and resource-aware compliance requirements. In: Meersman, R., et al. (eds.) OTM 2014. LNCS, vol. 8841, pp. 237–257. Springer, Heidelberg (2014). https://doi.org/10.1007/978-3-662-45563-0_14

    Chapter  Google Scholar 

  26. Taymouri, F., Carmona, J.: An evolutionary technique to approximate multiple optimal alignments. In: Weske, M., Montali, M., Weber, I., vom Brocke, J. (eds.) BPM 2018. LNCS, vol. 11080, pp. 215–232. Springer, Cham (2018). https://doi.org/10.1007/978-3-319-98648-7_13

    Chapter  Google Scholar 

  27. Van Der Aalst, W.: Data science in action. In: Van Der Aalst, W. (ed.) Process Mining, pp. 3–23. Springer, Heidelberg (2016). https://doi.org/10.1007/978-3-662-49851-4_1

    Chapter  Google Scholar 

  28. Van der Aalst, W., Adriansyah, A., van Dongen, B.: Replaying history on process models for conformance checking and performance analysis. Wiley Interdisc. Rev. Data Min. Knowl. Discov 2(2), 182–192 (2012)

    Article  Google Scholar 

  29. Dongen, B.F.: Efficiently computing alignments. In: Weske, M., Montali, M., Weber, I., vom Brocke, J. (eds.) BPM 2018. LNCS, vol. 11080, pp. 197–214. Springer, Cham (2018). https://doi.org/10.1007/978-3-319-98648-7_12

    Chapter  Google Scholar 

  30. van Hee, K., Sidorova, N., Voorhoeve, M.: Soundness and separability of workflow nets in the stepwise refinement approach. In: van der Aalst, W.M.P., Best, E. (eds.) ICATPN 2003. LNCS, vol. 2679, pp. 337–356. Springer, Heidelberg (2003). https://doi.org/10.1007/3-540-44919-1_22

    Chapter  MATH  Google Scholar 

  31. Van Hee, K., Sidorova, N., Voorhoeve, M.: Resource-constrained workflow nets. Fundamenta Informaticae 71(2, 3), 243–257 (2006)

    MathSciNet  MATH  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Department of Mathematics and Computer Science, Eindhoven University of Technology, Eindhoven, The Netherlands

    Dominique Sommers, Natalia Sidorova & Boudewijn van Dongen

Authors
  1. Dominique Sommers
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Natalia Sidorova
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Boudewijn van Dongen
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Dominique Sommers .

Editor information

Editors and Affiliations

  1. University of Milano-Bicocca, Milano, Italy

    Luca Bernardinello

  2. Paris 13 University, Villetaneuse, France

    Laure Petrucci

Rights and permissions

Reprints and permissions

Copyright information

© 2022 Springer Nature Switzerland AG

About this paper

Check for updates. Verify currency and authenticity via CrossMark

Cite this paper

Sommers, D., Sidorova, N., van Dongen, B. (2022). Aligning Event Logs to Resource-Constrained \(\nu \)-Petri Nets. In: Bernardinello, L., Petrucci, L. (eds) Application and Theory of Petri Nets and Concurrency. PETRI NETS 2022. Lecture Notes in Computer Science, vol 13288. Springer, Cham. https://doi.org/10.1007/978-3-031-06653-5_17

Download citation

  • DOI: https://doi.org/10.1007/978-3-031-06653-5_17

  • Published:

  • Publisher Name: Springer, Cham

  • Print ISBN: 978-3-031-06652-8

  • Online ISBN: 978-3-031-06653-5

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics

Search

Navigation