Please use this identifier to cite or link to this item:
http://hdl.handle.net/1942/21776
Title: | Calculating the Number of Unique Paths in a Block-Structured Process Model | Authors: | JANSSENSWILLEN, Gert DEPAIRE, Benoit JOUCK, Toon |
Issue Date: | 2016 | Source: | van der Aalst, Wil; Bergenthum, Robin; Carmona, Josep (Ed.). Proceedings of the International Workshop on Algorithms & Theories for the Analysis of Event Data 2016, p. 138-152 | Series/Report: | CEUR-Workshop Proceedings | Series/Report no.: | 1592 | Abstract: | Estimating the number of execution paths in a process model is a non-trivial task as one runs quickly into an combinatorial explosion of possible paths. This paper introduces a new algorithm to calculate the number of different execution paths for finite-behavior block-structured models in a computationally efficient way. Block functions are defined for the workflow constructs sequence, parallel, exclusive choice and finite loops, such that the amount of behavior in each block-construct can be computed efficiently. Subsequently, the block-structuredness of the model is exploited to efficiently calculate the number of unique paths in the model. The algorithm has been implemented for process trees, although the translation to other modeling notations is straightforward. An empirical analysis showed that the run-time of the algorithm is very low, and only slightly impacted by the complexity of the model. | Keywords: | process modeling; process mining; process trees; process model complexity | Document URI: | http://hdl.handle.net/1942/21776 | Link to publication/dataset: | http://ceur-ws.org/Vol-1592/paper10.pdf | Category: | C1 | Type: | Proceedings Paper | Validations: | vabb 2023 |
Appears in Collections: | Research publications |
Files in This Item:
File | Description | Size | Format | |
---|---|---|---|---|
paper10.pdf | Published version | 209.66 kB | Adobe PDF | View/Open |
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.