Document Server@UHasselt >
Research >
Research publications >

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, Benoît
Jouck, Toon
Issue Date: 2016
Citation: 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.
URI: http://hdl.handle.net/1942/21776
Link to publication: http://ceur-ws.org/Vol-1592/paper10.pdf
ISSN: 1613-0073
Category: C1
Type: Proceedings Paper
Appears in Collections: Research publications

Files in This Item:

Description SizeFormat
author version515.59 kBAdobe PDF

Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.