Efficient full compliance checking of concurrent components for business process models

Business process compliance checking is an NP-complete problem, due to con-currency and different mutually exclusive execution paths. Although the complexity of real life process models usually allows for a brute force approach, environments with limited resources or computational power (like for instance blockchain environments) cannot rely on brute force approaches due to the computational complexity of the problem. In this paper, we present an approach to efficiently check a subclass of problems involving concurrent sub-processes. Our approach reduces the computational complexity of concurrent sub-processes from combinatorial to exponential. We prove the correctness of the approach, we experimentally validate the results and evaluate the scalability of the approach. We show that our approach is a significant improvement for highly concurrent processes and easily outperforms existing brute force approaches.