Organisations model their processes using so-called business process models, to allow for verification of their correctness with respect to regulatory requirements and business rules. Automated methods for checking compliance, however, have to deal with the high complexity of the requirements as well as the significant size and quantity of process models in an organisation, which may prevent process models from being checked efficiently and timely. This paper provides a computational complexity analysis of the problem of proving regulatory compliance of process models. We investigate the computational complexity of each variant of the problem resulting from a combination of three binary properties associated to the regulatory framework, determining the regulatory requirements that a process model needs to follow to be compliant. These binary properties are whether the framework contains one or multiple obligations, whether the obligations are global or conditional, and whether only literals or formulae can be used to describe the obligations. For each variant of the problem we study the computational complexity of proving full compliance, partial compliance, and non-compliance. This analysis allows to understand the specific features of the problem leading to intractability issues, thus potentially guiding future research towards developing feasible solutions for the problem in practical settings.
翻译:各组织采用所谓的业务流程模型模拟其程序,以便核查其是否符合监管要求和业务规则; 然而,检查遵守情况的自动化方法必须处理要求的高度复杂性以及一个组织内程序模型的庞大规模和数量,这可能妨碍对流程模型进行有效和及时的检查; 本文对证明流程模型遵守监管规定的问题进行计算复杂性分析; 我们调查了与监管框架有关的三个二元属性组合所产生的问题的每个变量的计算复杂性,确定一个流程模型需要遵循的监管要求。 这些二元属性是框架是否包含一项或多项义务,无论是全球义务还是有条件义务,以及是否只能使用字面或公式来描述义务。 对于我们研究的问题的每一种变量,我们研究了证明完全遵守、部分遵守和不遵守情况的计算复杂性。这种分析有助于了解导致易被吸引问题的问题的具体特征,从而有可能指导未来研究如何在实际环境中为问题制定可行的解决办法。