Business Process Compliance with impact constraints

Business Process Compliance is a family of methods to evaluate Business Processes in terms of the existence of one execution (one trace) that does not violate constraints superimposed on the process itself. The dual version is formulated as the superimposition of a set of constraints and consequent evaluation of the process for all the executions. These problems are relevant to a large part of actual applications, especially those in the context of regulatory compliance where we aim at verifying the process against a normative background (including, for instance, soft ones, such as guidelines, product specification, and product standards) or goals fixed by the owner of the process. In this paper we discuss one new type of compliance, that is impact compliance, devised to verify when a process respects a set of constraints, to establish that certain amounts, measuring the undesired effects of the tasks executed to implement the process, are below given limits. In the current literature on Business Process Management, Business Process Analysis, and Business Process Compliance, this type of compliance checking process has not yet been addressed. As we demonstrate in this paper, this problem is significant and complex to address. In particular, we show that the checking problems described above are, under certain structural conditions, polynomially solvable on deterministic machines. In general, however, the first problem is NP-complete whilst the second is polynomially solvable on deterministic machines.