On Determining the AND-OR Hierarchy in Workflow Nets

• Autorzy: Sroka J. , Hidders J.

Identyfikatory

DOI

10.3233/FI-2017-1599

• Języki publikacji: EN

Abstrakty

EN

This paper presents a notion of reduction where a WF net is transformed into a smaller net by iteratively contracting certain well-formed subnets into single nodes until no more of such contractions are possible. This reduction can reveal the hierarchical structure of a WF net, and since it preserves certain semantic properties such as soundness, can help with analysing and understanding why a WF net is sound or not. The reduction can also be used to verify if a WF net is an AND-OR net. This class of WF nets was introduced in earlier work, and arguably describes nets that follow good hierarchical design principles. It is shown that the reduction is confluent up to isomorphism, which means that despite the inherent non-determinism that comes from the choice of subnets that are contracted, the final result of the reduction is always the same up to the choice of the identity of the nodes. Based on this result, a polynomial-time algorithm is presented that computes this unique result of the reduction. Finally, it is shown how this algorithm can be used to verify if a WF net is an AND-OR net.

Słowa kluczowe

EN

semantics; algorithms; isomorphisms; Petri nets; evaluation nets

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2017
• Tom: Vol. 156, nr 1
• Strony: 95--123
• Opis fizyczny: Bibliogr. 37 poz., rys.

Twórcy

autor

Sroka J.

• Institute of Informatics, University of Warsaw, Poland

autor

Hidders J.

• Vrije Universiteit Brussel, Belgium

Bibliografia

• [1] Best E, Devillers RR, and Esparza J. General refinement and recursion operators for the Petri box calculus. In P. Enjalbert, A. Finkel, and K. W. Wagner, editors, STACS 93, Proc. of the 10th Annual Symposium on Theoretical Aspects of Computer Science, volume 665 of Lecture Notes in Computer Science, Springer, February 25-27 1993, pp. 130–140. URL https://doi.org/10.1007/3-540-56503-5_16.
• [2] Chrzastowski-Wachtel P, Benatallah B, Hamadi R, O’Dell M, and Susanto A. A top-down Petri net-based approach for dynamic workflow modeling. In Proceedings of BPM’03, Springer-Verlag, 2003, pp. 336–353. URL https://doi.org/10.1007/3-540-44895-0_23.
• [3] Chrzastowski-Wachtel P, Golab P, and Lewinski B. Sound recoveries of structural workflows with synchronization. In M. S. Szczuka, L. Czaja, and M. Kacprzak, editors, Proceedings of the 22nd International Workshop on Concurrency, Specification and Programming, Warsaw, Poland, volume 1032 of CEUR Workshop Proceedings, CEUR-WS.org. 2013, pp. 73–87.
• [4] Chrząstowski-Wachtel P. Determining sound markings in structured nets. Fundam. Inf., 2006;72(1-3):65–79. URL http://dl.acm.org/citation.cfm?id=2369376.2369382.
• [5] De Roure D, Goble C, and Stevens R. The design and realisation of the virtual research environment for social sharing of workflows. Future Generation Computer Systems, 2009;25(5):561–567. URL https://doi.org/10.1016/j.future.2008.06.010.
• [6] Dehnert J, and Rittgen P. Relaxed soundness of business processes. In K. Dittrich, A. Geppert, and M. Norrie, editors, Advanced Information Systems Engineering, volume 2068 of Lecture Notes in Computer Science, Springer Berlin Heidelberg, 2001, pp. 157–170. URL https://doi.org/10.1007/3-540-45341-5_11.
• [7] Devillers R, Klaudel H, and Riemann R. General refinement for high level Petri nets. Foundations of Software Technology and Theoretical Computer Science, volume 1346 of Lecture Notes in Computer Science, 1997, pp. 297–311. URL https://doi.org/10.1007/BFb0058038.
• [8] Esparza J, and Silva M. Top-down synthesis of live and bounded free choice nets. In G. Rozenberg, editor, Advances in Petri Nets 1991, Papers from the 11th International Conference on Applications and Theory of Petri Nets, volume 524 of Lecture Notes in Computer Science. Springer, 1990, pp. 118–139. URL https://doi.org/10.1007/BFb0019972.
• [9] Fahland D, Favre C, Koehler J, Lohmann N, Völzer H, and Wolf K. Analysis on demand: Instantaneous soundness checking of industrial business process models. Data Knowl. Eng., 2011;70(5):448–466. URL https://doi.org/10.1016/j.datak.2011.01.004.
• [10] Flender C, and Freytag T. Visualizing in the soundness of workflow nets. In Bericht 267, Tagungsband des 13. Workshops Algorithmen und Werkzeuge für Petri-Netze, AWPN’06, FBI-HH-B-267/06, 2006, pp. 47–53.
• [11] Gold R. Reductions of control flow graphs. International Journal of Computer, Electrical, Automation, Control and Information Engineering, 2014;8(3):427–434.
• [12] Huet G. Confluent reductions: Abstract properties and applications to term rewriting systems: Abstract properties and applications to term rewriting systems. J. ACM, 1980;27(4):797–821. doi:10.1145/322217.322230.
• [13] Keller G, Nuttigens M, and Scheer A-W. Semantische prozessmodellierung auf der grundlage: Ereignisgesteuerter prozessketten (EPK). Veröffentlichungen des Instituts für Wirtschaftsinformatik, 89, Januar 1992. https://books.google.pl/books?id=MIKftgAACAAJ.
• [14] Martens A. On compatibility of web services. Petri Net Newsletter, 2003;65:12–20.
• [15] Martens A. Analyzing web service based business processes. In Proceedings of the 8th International Conference, Held As Part of the Joint European Conference on Theory and Practice of Software Conference on Fundamental Approaches to Software Engineering, FASE’05, Berlin, Heidelberg, Springer-Verlag. 2005, pp. 19–33. URL https://doi.org/10.1007/978-3-540-31984-9_3.
• [16] Murata T. Petri nets: Properties, analysis and applications. Proc. of the IEEE, 77(4):541–580, Apr 1989.
• [17] Object Management Group (OMG). Business Process Model and Notation (BPMN) Version 2.0. Technical report, http://www.omg.org/spec/BPMN/2.0/, January 2011.
• [18] Petri CA, and Reisig W. Petri net. Scholarpedia, 2008;3(4):64–77.
• [19] Polyvyanyy A, García-Bañuelos L, and Dumas M. Structuring acyclic process models. Information Systems, 2012;37(6):518–538. doi:10.1016/j.is.2011.10.005.
• [20] Polyvyanyy A, Weidlich M, and Weske M. Connectivity of workflow nets: the foundations of stepwise verification. Acta Inf., 2011;48(4):213–242. URL https://doi.org/10.1007/s00236-011-0137-8.
• [21] Puhlmann F, and Weske M. Investigations on Soundness Regarding Lazy Activities. In S. Dustdar, J. Fiadeiro, and A. Sheth, editors, International Conference on Business Process Management (BPM 2006), volume 4102 of Lecture Notes in Computer Science, Springer-Verlag, Berlin, 2006, pp. 145–160. URL https://doi.org/10.1007/11841760_11.
• [22] Sroka J, Chrzastowski-Wachtel P, and Hidders J. On generating *-sound nets with substitution. Application of Concurrency to System Design, International Conference on, 2011, pp. 3–12. doi:10.1109/ACSD.2011.26.
• [23] Sroka J. and Hidders J. On generating *-sound nets with substitution. Inf. Syst., 2014;40:32–46. URL https://doi.org/10.1016/j.is.2013.10.004.
• [24] Suzuki L, and Murata T. A method for stepwise refinement and abstraction of Petri nets. Journal of Computer and System Sciences, 1983;27(1):51–76. URL https://doi.org/10.1016/0022-0000(83)90029-6.
• [25] Trčka N, Aalst WM, and Sidorova N. Data-flow anti-patterns: Discovering data-flow errors in workflows. In Proceedings of the 21st International Conference on Advanced Information Systems Engineering, CAiSE ’09, Springer-Verlag. Berlin, Heidelberg, 2009, pp. 425–439. URL https://doi.org/10.1007/978-3-642-02144-2_34.
• [26] van der Aalst W, Michelis GD, and Ellis C. editors. Structural Analysis of Workflow Nets with Shared Resources, volume 98/7 of Computer science reports, 1998.
• [27] van der Aalst WMP. The application of Petri nets to workflow management. Journal of Circuits, Systems, and Computers, 1998;8(1):21–66. doi:10.1142/S0218126698000043.
• [28] van der Aalst WMP, ter Hofstede AHM, Kiepuszewski B, and Barros AP. Workflow patterns. Distrib. Parallel Databases, 2003;14(1):5–51. URL https://doi.org/10.1023/A:1022883727209.
• [29] van der Aalst WMP, van Hee KM, ter Hofstede AHM, Sidorova N, Verbeek HMW, Voorhoeve M, and Wynn MT. Soundness of workflow nets: classification, decidability, and analysis. Formal Asp. Comput., 2011;23(3):333–363. URL https://doi.org/10.1007/s00165-010-0161-4.
• [30] van der Toorn R. Component-based software design with Petri nets: an approach based on inheritance of behavior. PhD thesis, Eindhoven University of Technology, Eindhoven, The Netherlands, 2004. PhD thesis.
• [31] van Hee K, Sidorova N, and Voorhoeve M. Generalised Soundness of Workflow Nets Is Decidable. In J. Cortadella and W. Reisig, editors, Application and Theory of Petri Nets 2004, volume 3099 of Lecture Notes in Computer Science, Springer-Verlag, Berlin, 2004, pp. 197–215. URL https://doi.org/10.1007/978-3-540-27793-4_12.
• [32] van Hee KM, Sidorova N, and Voorhoeve M. Soundness and separability of workflow nets in the stepwise refinement approach. In W. M. P. van der Aalst and E. Best, editors, ICATPN, volume 2679 of Lecture Notes in Computer Science, Springer, 2003, pp. 337–356. URL https://doi.org/10.1007/3-540-44919-1_22.
• [33] Vanhatalo J, Völzer H, and Koehler J. The refined process structure tree. In M. Dumas, M. Reichert, and M.-C. Shan, editors, Business Process Management, volume 5240 of Lecture Notes in Computer Science, Springer Berlin Heidelberg, 2008, pp. 100–115. URL https://doi.org/10.1007/978-3-540-85758-7_10.
• [34] Vanhatalo J, Völzer H, and Koehler J. The refined process structure tree. Data Knowl. Eng., 68(9):793–818, Sept. 2009.
• [35] Verbeek HMW. Verification of WF-nets. PhD thesis, Eindhoven University of Technology, Eindhoven, The Netherlands, 2004. PhD thesis.
• [36] Verbeek HMW, Basten T, and van der Aalst WMP. Diagnosing workflow processes using Woflan. The Computer Journal, 2001;44(4):246–279. doi:DOI: 10.1093/comjnl/44.4.246.
• [37] Wang Z, and Wei D. Modeling complex system using T-subnet based hierarchical Petri nets. Journal of Computers, 2009;4(9):829–836. doi:10.4304/jcp.4.9.829-836.

Uwagi

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