Approximate compliance checking for annotated process models

We describe a method for validating whether the states reached by a process are compliant with a set of constraints. This serves to (i) check the compliance of a new or altered process against the constraints base, and (ii) check the whole process repository against a changed constraints base, e.g., when new regulations come into being. For these purposes we formalize a particular class of compliance rules as well as annotated process models, the latter by combining a notion from the workflow literature with a notion from the AI actions and change literature. The compliance rules in turn pose restrictions on the desirable states. Each rule takes the form of a clausal constraint, i.e., a disjunction of literals. If for a given state there is a grounded clause none of whose literals are true, then the constraint is violated and indicates non-compliance. Checking whether a process is compliant with the rules involves enumerating all reachable states and is in general a hard search problem. Since long waiting times undesirable, it is important to explore restricted classes and approximate methods. We present a polynomial-time algorithm that, for a particular class of processes, computes the sets of literals that are necessarily true at particular points during process execution. Based on this information, we devise two approximate compliance checking methods. One of these is sound but not complete (it guarantees to find only non-compliances, but not to find all non-compliances); the other method is complete but not sound. We sketch how one can trace the state evolution back to the process activities which caused the (potential) non-compliance, and hence provide the user with some error diagnosis.