A novel graph reduction algorithm to identify structural conflicts

Abstract

The algorithm is based on a set of graph reduction rules to identify the deadlock and lack of synchronization conflicts that could compromise the correct execution of a workflow. However, an example, which is apparently correct but cannot be reduced by the rules, shows the incompleteness of the algorithm. In this paper, we present a complete and minimal set of rules and a novel algorithm to implement the identification of structural conflicts in process models. The correctness and completeness of the algorithm is strictly proved. Finally, the complexity of the algorithm is analyzed.