On Generating Hierarchical Workflow Nets and their Extensions and Verifying Hierarchicality

• Autorzy: Sroka J. , Chrząstowski-Wachtel P. , Hidders J.

Identyfikatory

DOI

10.3233/FI-2015-1280

• Języki publikacji: EN

Abstrakty

EN

For designing and analyzing complex workflow nets the notion of hierarchical decomposition can be essential for keeping the structure of the workflow comprehensible. In this paper we study two classes of nets: hierarchical nets and extended hierarchical nets. The first have a simple hierarchical structure and can be defined in terms of five simple refinement rules. We show that for arbitrary nets it can be easily verified if they can be constructed this way, thus confirming their good design and the properties following from it. As we prove, this can be done by performing the refinements in reverse, i.e., by contracting subnets into single nodes. It is shown that the choice of the contracted subnet does not change the final result of the process, and therefore this procedure for checking the hierarchical structure requires no back-tracking. The second class, extended hierarchical nets, is an extension of the first class where two types of extra refinements are introduced that allow to indicate (1) the synchronization between two parallel running subworkflows or (2) the transfer of a thread from one subworkflow to another one. These refinements come with natural and necessary preconditions that ensure that result is still a sound workflow net. In case (1) where we want to synchronize two actions in two subworkflows, we should convince ourselves that the subworkflows represent parallel threads which always execute together, otherwise a deadlock could easily arise. Dually, in case (2), if after the moment that a choice was made between two subworkflows we at a later point in the workflow want to allow a transfer between them, this can be done safely provided that we did not enter any thread fork in the meantime. We show that the class of extended hierarchical nets, which is defined by adding these two additional types of refinement, is a proper superset of the hierarchical nets, but still all such nets exhibit the correctness property of *-soundness. We do this by showing that the class is a proper subset of the AND-OR nets which were in earlier work shown to have this property.

Słowa kluczowe

EN

workflow net; Petri net; soundness; hierarchical nets; extended hierarchical nets

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2015
• Tom: Vol. 141, nr 4
• Strony: 367--398
• Opis fizyczny: Bibliogr. 60 poz., rys.

Twórcy

autor

Sroka J.

• Institute of Informatics University of Warsaw, Poland

autor

Chrząstowski-Wachtel P.

• Institute of Informatics University of Warsaw, Poland

autor

Hidders J.

• Delft University of Technology, The Netherlands

Bibliografia

• [1] Structural Analysis of Workflow Nets with Shared Resources, vol. volume 98/7 of Computer science reports, 1998.
• [2] van der Aalst, W. M. P.: The Application of Petri Nets to Workflow Management., Journal of Circuits, Systems, and Computers, 8(1), 1998, 21–66.
• [3] van der Aalst, W. M. P., Best, E., Eds.: Applications and Theory of Petri Nets 2003, 24th International Conference, ICATPN 2003, Eindhoven, The Netherlands, June 23-27, 2003, Proceedings, vol. 2679 of Lecture Notes in Computer Science, Springer, 2003, ISBN 3-540-40334-5.
• [4] van der Aalst, W. M. P., van Hee, K. M., ter Hofstede, A. H. M., Sidorova, N., Verbeek, H. M. W., Voorhoeve, M., Wynn, M. T.: Soundness of workflow nets: classification, decidability, and analysis, Formal Asp. Comput., 23(3), 2011, 333–363.
• [5] Barkaoui, K., Ben Ayed, R.: Uniform Verification of Workflow Soundness, Transactions of the Institute of Measurement and Control Journal, 31, 2010, 1–16.
• [6] Barkaoui, K., Ben Ayed, R., Sbai, Z.: Workflow Soundness Verification Based on Structure Theory of Petri Nets, International Journal of Computing & Information Sciences (IJCIS journal), 5(1), 2007, 51–62.
• [7] Berthelot, G.: Transformations and Decompositions of Nets, in: Brauer et al. [12], 359–376.
• [8] Best, E., Devillers, R., Hall, J. G.: The Box Calculus: A New Causal Algebra with Multi-label Communication, Advances in Petri Nets 1992, The DEMON Project, Springer-Verlag, London, UK, UK, 1992, ISBN 3-540-55610-9.
• [9] Best, E., Devillers, R. R., Esparza, J.: General Refinement and Recursion Operators for the Petri Box Calculus., STACS (P. Enjalbert, A. Finkel, K. W. Wagner, Eds.), 665, Springer, 1993, ISBN 3-540-56503-5.
• [10] Best, E., Koutny, M.: A Refined View of the Box Algebra, Application and Theory of Petri Nets 1995, 16th International Conference, Turin, Italy, June 26-30, 1995, Proceedings (G. D. Michelis, M. Diaz, Eds.), 935, Springer, 1995.
• [11] Brauer,W., Gold, R., Vogler,W.: A survey of behaviour and equivalence preserving refinements of Petri nets, Advances in Petri Nets 1990, 1991, 1–46.
• [12] Brauer, W., Reisig, W., Rozenberg, G., Eds.: Petri Nets: Central Models and Their Properties, Advances in Petri Nets 1986, Part I, Proceedings of an Advanced Course, Bad Honnef, 8.-19. September 1986, vol. 254 of Lecture Notes in Computer Science, Springer, 1987, ISBN 3-540-17905-4.
• [13] Chrzastowski-Wachtel, P., Benatallah, B., Hamadi, R., O’Dell, M., Susanto, A.: A top-down Petri net-based approach for dynamic workflow modeling, Proceedings of BPM’03, Springer-Verlag, 2003, ISBN 3-540-40318-3.
• [14] Chrzastowski-Wachtel, P., Golab, P., Lewinski, B.: Sound Recoveries of StructuralWorkflows with Synchronization, in: Szczuka et al. [52], 73–87.
• [15] Chrza¸stowski-Wachtel, P.: Determining Sound Markings in Structured Nets, Fundam. Inf., 72(1-3), April 2006, 65–79, ISSN 0169-2968.
• [16] Desel, J., Esparza, J.: Free Choice Petri Nets (Cambridge Tracts in Theoretical Computer Science), Cambridge University Press, New York, NY, USA, 2005, ISBN 0521019451.
• [17] Devillers, R., Klaudel, H., Riemann, R.: General refinement for high level Petri nets, Foundations of Software Technology and Theoretical Computer Science, 1997, 297–311.
• [18] Devillers, R., Klaudel, H., Riemann, R.-C.: General parameterised refinement and recursion for the M-net calculus, Theoretical Computer Science, 300(1–3), 2003, 259 – 300, ISSN 0304-3975.
• [19] Dumas, M., Rosa, M. L., Mendling, J., Mäesalu, R., Reijers, H. A., Semenenko, N.: Understanding Business Process Models: The Costs and Benefits of Structuredness, Advanced Information Systems Engineering - 24th International Conference, CAiSE 2012, Gdansk, Poland, June 25-29, 2012. Proceedings (J. Ralyté, X. Franch, S. Brinkkemper, S. Wrycza, Eds.), 7328, Springerr, 2012.
• [20] Esparza, J.: Reduction and synthesis of live and bounded free choice Petri nets, Inf. Comput., 114(1), 1994, 50–87, ISSN 0890-5401.
• [21] Esparza, J., Lakos, C., Eds.: Applications and Theory of Petri Nets 2002, 23rd International Conference, ICATPN 2002, Adelaide, Australia, June 24-30, 2002, Proceedings, vol. 2360 of Lecture Notes in Computer Science, Springer, 2002, ISBN 3-540-43787-8.
• [22] Esparza, J., Silva, M.: On the analysis and synthesis of free choice systems., in: Rozenberg [47], 243–286.
• [23] Esparza, J., Silva, M.: Top-down synthesis of live and bounded free choice nets., Applications and Theory of Petri Nets (G. Rozenberg, Ed.), 524, Springer, 1990, ISBN 3-540-54398-8.
• [24] Esparza, J., Silva, M.: Compositional Synthesis of Live and Bounded Free Choice Petri Nets., CONCUR (J. C. M. Baeten, J. F. Groote, Eds.), 527, Springer, 1991, ISBN 3-540-54430-5.
• [25] Fahland, D., Favre, C., Jobstmann, B., Koehler, J., Lohmann, N., Völzer, H., Wolf, K.: Instantaneous Soundness Checking of Industrial Business Process Models, in: Business Process Management (U. Dayal, J. Eder, J. Koehler, H. Reijers, Eds.), vol. 5701 of Lecture Notes in Computer Science, Springer Berlin Heidelberg, 2009, ISBN 978-3-642-03847-1, 278–293.
• [26] Fernández, C.: Net Topology I, II, St. Augustin: Gesellschaft für Mathematik und Datenverarbeitung Bonn, Interner Bericht ISF-75–09, September 1975.
• [27] van Hee, K., Hidders, J., Houben, G.-J., Paredaens, J., Thiran, P.: On the relationship between workflow models and document types, Inf. Syst., 34, March 2009, 178–208, ISSN 0306-4379.
• [28] van Hee, K., Sidorova, N., Voorhoeve, M.: Soundness and Separability of Workflow Nets in the Stepwise Refinement Approach., Proceedings of the 24th International Conference on Applications and Theory of Petri Nets (ICATPN 2003), Eindhoven, The Netherlands, June 23-27, 2003 — Volume 2679 of Lecture Notes in Computer Science / Wil M. P. van der Aalst and Eike Best (Eds.), Springer-Verlag, June 2003.
• [29] van Hee, K. M., Mooij, A. J., Sidorova, N., van der Werf, J. M.: Soundness-Preserving Refinements of Service Compositions, in: Web Services and Formal Methods (M. Bravetti, T. Bultan, Eds.), vol. 6551 of Lecture Notes in Computer Science, Springer Berlin Heidelberg, 2011, ISBN 978-3-642-19588-4, 131–145.
• [30] van Hee, K. M., Sidorova, N., Voorhoeve, M.: Soundness and Separability of Workflow Nets in the Stepwise Refinement Approach, in: van der Aalst and Best [3], 337–356.
• [31] van Hee, K. M., Sidorova, N., van derWerf, J. M.: Refinement of Synchronizable Places with Multi-workflow Nets, Fundamenta Informaticae, 122(1), 01 2013, 59–83.
• [32] Huang, H., Cheung, T. Y., Mak, W. M.: Structure and behavior preservation by Petri-net-based refinements in system design, Theoretical Computer Science, 328(3), December 2004, 245–269.
• [33] Jackson, M.: Software Requirements &Amp; Specifications: A Lexicon of Practice, Principles and Prejudices, ACM Press/Addison-Wesley Publishing Co., New York, NY, USA, 1995, ISBN 0-201-87712-0.
• [34] Jackson, M. A.: Principles of Program Design, Academic Press, Inc., Orlando, FL, USA, 1975, ISBN 0123790506.
• [35] Jackson, M. A.: System Development (Prentice-Hall International Series in Computer Science), Prentice-Hall, Inc., Upper Saddle River, NJ, USA, 1983, ISBN 0138803285.
• [36] Jacquet, H., Klempien-Hinrichs, R.: Node Replacement in Hypergraphs: Translating NCE Rewriting into the Pullback Approacht, in: Theory and Application of Graph Transformations (H. Ehrig, G. Engels, H.-J. Kreowski, G. Rozenberg, Eds.), vol. 1764 of Lecture Notes in Computer Science, Springer Berlin Heidelberg, 2000, ISBN 978-3-540-67203-6, 117–130.
• [37] Klaudel, H., Pommereau, F.: M-nets: a survey, Acta Informatica, 45(7-8), 12 2009, 537–564.
• [38] Köhler, M., Moldt, D., Rölke, H.: Modelling mobility and mobile agents using nets within nets, Proceedings of the 24th International Conference on Application and Theory of Petri Nets 2003 (ICATPN 2003) (W. van der Aalst, E. Best, Eds.), 2679, 2003.
• [39] Köhler, M., Rölke, H.: Dynamic Transition Refinement, Electronic Notes in Theoretical Computer Science, 175, June 2007, 119–134.
• [40] Michelis, G. D., Diaz, M., Eds.: Application and Theory of Petri Nets 1995, 16th International Conference, Turin, Italy, June 26-30, 1995, Proceedings, vol. 935 of Lecture Notes in Computer Science, Springer, 1995, ISBN 3-540-60029-9.
• [41] Padberg, J., Gajewsky, M., Ermel, C.: Rule-based refinement of high-level nets preserving safety properties, Science of Computer Programming, 40(1), 2001, 97–118.
• [42] Peng, Z., Mei, Q., Xikui, L.: The Behavior Properties of Refinement of Petri Nets and Application in Parallel Programming, Computer Science and Information Engineering, World Congress on, 3, 2009, 330–333.
• [43] Petri, C. A., Reisig, W.: Petri net, Scholarpedia, 3(4), 2008, 64–77.
• [44] Polyvyanyy, A., García-Bañuelos, L., Dumas, M.: Structuring acyclic process models, Information Systems, 37(6), 2012, 518 – 538, ISSN 0306-4379.
• [45] Qi, Z., You, J., Mao, H.: P Systems and Petri Nets, Membrane Computing, 2004, 819–847.
• [46] Ralyté, J., Franch, X., Brinkkemper, S., Wrycza, S., Eds.: Advanced Information Systems Engineering - 24th International Conference, CAiSE 2012, Gdansk, Poland, June 25-29, 2012. Proceedings, vol. 7328 of Lecture Notes in Computer Science, Springer, 2012, ISBN 978-3-642-31094-2.
• [47] Rozenberg, G., Ed.: Advances in Petri Nets 1990 [10th International Conference on Applications and Theory of Petri Nets, Bonn, Germany, June 1989, Proceedings], vol. 483 of Lecture Notes in Computer Science, Springer, 1991, ISBN 3-540-53863-1.
• [48] Sroka, J., Chrzastowski-Wachtel, P., Hidders, J.: On Generating *-Sound Nets with Substitution, Application of Concurrency to System Design, International Conference on, 2011, 3–12, ISSN 1550-4808.
• [49] Sroka, J., Hidders, J.: On generating *-sound nets with substitution, Inf. Syst., 40, 2014, 32–46.
• [50] Stork, D. G., van Glabbeek, R. J.: Token-Controlled Place Refinement in Hierarchical Petri Nets with Application to Active Document Workflow, in: Esparza and Lakos [21], 394–413.
• [51] Suzuki, I., Murata, T.: A method for stepwise refinement and abstraction of Petri nets, Journal of Computer and System Sciences, 27(1), 1983, 51–76, ISSN 0022-0000.
• [52] Szczuka, M. S., Czaja, L., Kacprzak, M., Eds.: Proceedings of the 22nd International Workshop on Concurrency, Specification and Programming, Warsaw, Poland, vol. 1032 of CEUR Workshop Proceedings, CEURWS. org, 2013.
• [53] Trčka, N., Aalst,W. M., Sidorova, N.: Data-Flow Anti-patterns: Discovering Data-Flow Errors in Workflows, Proceedings of the 21st International Conference on Advanced Information Systems Engineering, CAiSE ’09, Springer-Verlag, Berlin, Heidelberg, 2009, ISBN 978-3-642-02143-5.
• [54] Valk, R.: Modelling of Task Flow in Systems of Functional Units, FBI Bericht FBI-HH-B-124/87, Universität Hamburg, Fachbereich Informatik, 1987.
• [55] Valk, R.: On Processes of Object Petri Nets, FBI Bericht FBI-HH-B-185/96, Universität Hamburg, Fachbereich Informatik, June 1996.
• [56] Valk, R.: Petri Nets as Token Objects - An Introduction to Elementary Object Nets, 19th International Conference on Application and Theory of Petri nets, Lisbon, Portugal (J. Desel, M. Silva, Eds.), number 1420, 1998, ISSN 0302-9743.
• [57] Van Der Aalst,W. M. P., Ter Hofstede, A. H. M., Kiepuszewski, B., Barros, A. P.: Workflow Patterns, Distrib. Parallel Databases, 14(1), July 2003, 5–51, ISSN 0926-8782.
• [58] Vanhatalo, J., Völzer, H., Koehler, J.: The Refined Process Structure Tree, in: Business Process Management (M. Dumas, M. Reichert, M.-C. Shan, Eds.), vol. 5240 of Lecture Notes in Computer Science, Springer Berlin Heidelberg, 2008, ISBN 978-3-540-85757-0, 100–115.
• [59] Wang, Z., Wei, D.: Modeling Complex System Using T-subnet based Hierarchical Petri Nets, Journal of Computers, 4(9), Sep 2009, 829–836.
• [60] Wynn, M. T., Verbeek, H. M. W., van der Aalst, W. M. P., ter Hofstede, A. H. M., Edmond, D.: Reduction rules for YAWL workflows with cancellation regions and OR-joins, Inf. Softw. Technol., 51(6), 2009, 1010–1020, ISSN 0950-5849.