Proving Regulatory Compliance: Business Processes, Logic, Complexity

Doctoral thesis (2015)

The problem of proving regulatory compliance of a business process model is composed of two main elements. One of these elements is the business process model, which provides a formal compact description ... [more ▼]

The problem of proving regulatory compliance of a business process model is composed of two main elements. One of these elements is the business process model, which provides a formal compact description of the available executions capable of achieving a given business objective. The other element is the regulatory framework that the business process must follow, describing the compliance requirements given by the law or by a company’s own internal regulations. The problem consists of verifying whether a given business process model is compliant with the regulatory framework, which is carried out by verifying whether the executions of the model comply with the requirements of the regulatory framework. Solutions to prove the regulatory compliance of business processes have been already proposed in the past. Some solutions disregard the computational complexity aspect of the problem, while other solutions either solve a simplified version of the problem efficiently or provide approximate solutions for the general one. However, none of these solutions have formally studied the computational complexity of the problem of proving regulatory compliance. This thesis addresses that issue, showing in addition why efficient solutions of the general problem are not possible. In particular I study the computational complexity of a problem of proving regulatory compliance whose regulatory framework is defined using conditional obligations. The approach I adopt to represent the compliance requirement is semantically similar to some of the existing solutions proposed by other researchers, such as van der Aalst and many others, who adopts linear temporal logic over finite traces, or different variants of such temporal logic, to define the compliance requirements. More precisely, the approach used in the present thesis adopts propositional logic as base logic, and defines the semantics of the regulatory framework in a similar way as Process Compliance Logic introduced by Governatori and Rotolo. The study of the computational complexity of the problem is approached by dividing it in sub-classes and then combining their analysis to obtain the result for the target problem. The division is done according to three features of the regulatory framework. These features define whether the framework is composed of a single or a set of obligations, whether the obligations are conditional and whether violations can be compensated. These features can be omitted to identify simpler sub-classes of the problem. After having identified the different sub-classes of the problem, I study the computational complexity of some of these sub-classes and combine the results obtained to identify the computational complexity of the general problem tackled in the present thesis, where each of the three features identified are used to describe the compliance requirements. The results of the computational complexity analysis show that proving the existence of an execution of a business process compliant with the regulatory framework is an NP-complete problem. Differently proving that for all of the executions of a business process model, they are either compliant or not with the regulatory framework, is a coNP-complete problem. The results show that combining the two elements composing the problem of proving regulatory compliance, the process model and the regulatory framework, which are tractable when considered individually, leads to an intractable problem. In addition to the computational complexity results, the analysis provided in the thesis has also shown that tractable sub-classes of the problem, where the computational complexity is at most polynomial with respect to the size of the input, can be obtained by trivialising the expressivity of either one of the elements composing the problem. However the expressivity of these sub-classes is limited. Thus I identify a different tractable sub-class of the problem by weakening the expressivity of both elements composing the problem, but where each element is not trivialised as for the other sub-classes. Whether the sub-class identified can be considered expressive is arguable, however it represents a first step towards identifying a sub-class of the problem being both tractable and expressive, taking into account the limitation of employing propositional logic as base logic. [less ▲]

Business Process Regulatory Compliance is Hard

in IEEE Transactions on Services Computing (2015), 8(6), 958-970

Verifying whether a business process is compliant with a regulatory framework is a difficult task. In the present paper we prove the hardness of the business process regulatory compliance problem by ... [more ▼]

Verifying whether a business process is compliant with a regulatory framework is a difficult task. In the present paper we prove the hardness of the business process regulatory compliance problem by taking into account a sub-problem of the general problem. This limited problem allows to verify only the compliance of structured processes with respect to a regulatory framework composed of a set of conditional obligations including a deadline. Experimental evidence from existing studies shows that compliance is a difficult task. In this paper, despite considering a sub-problem of the general problem, we provide some theoretical evidence of the difficulty of the task. In particular we show that the source of the complexity lies in the core language of verifying conditional obligations with a deadline. We prove that for this simplified case verifying partial compliance belongs to the class of NP-complete problems, and verifying full compliance belongs to the class of coNP-complete problems. Thus by proving the difficulty of a simplified compliance problem we prove that the general problem of verifying business process regulatory compliance is hard. [less ▲]

Detecting Deontic Conflicts in Dynamic Settings

in Cariani, Fabrizio; Grossi, Davide; Meheus, Joke (Eds.) et al Deontic Logic and Normative Systems 12th International Conference, DEON 2014, Ghent, Belgium, July 12-15, 2014. Proceedings (2014)

Regulations, through the use of obligations and permissions, are widely used in modern society to define acceptable behaviours. Thus it is indeed important that these regulations do not conflict with each ... [more ▼]

Regulations, through the use of obligations and permissions, are widely used in modern society to define acceptable behaviours. Thus it is indeed important that these regulations do not conflict with each other and contain contradicting obligations. In the present paper we focus on identifying conflicts between obligations in dynamic settings. We first show the need of an alternative semantics rather than the more classic modelled by standard deontic logic. Second we introduce a new semantics for the obligations capable of representing and reasoning about them in these dynamic settings, and lastly we use it to identify the necessary and sufficient conditions to identify conflicting obligations. [less ▲]

Integrating Legal-URN and Eunomos: towards a comprehensive compliance management solution

in Proceedings of AI Approaches to the Complexity of Legal Systems (AICOL 2013) (2014)

Towards an Abstract Framework for Compliance

in Bagheri, Ebrahim; Gasevic, Dragan; Halle, Sylvain (Eds.) et al Proceedings of the 17th IEEE International EDOC 2013 Conference Workshops, Vancouver, Canada, 9 September 2013. (2013, September 09)

The present paper aims at providing an abstract framework to define the regulatory compliance problem. In particular we show how the framework can be used to solve the problem of deciding whether a ... [more ▼]

The present paper aims at providing an abstract framework to define the regulatory compliance problem. In particular we show how the framework can be used to solve the problem of deciding whether a structured process is compliant with a single regulation, which is composed of a primary obligation and a chain of compensations. [less ▲]

Visualizing Normative Systems: an Abstract Approach

in Agotnes, Thomas; Broersen, Jan; Elgesem, Dag (Eds.) Deontic Logic in Computer Science - 11th International Conference, DEON 2012, Bergen, Norway, July 16-18, 2012. Proceedings (2012)

Abstract normative systems allow to reason with norms even when their content is not detailed. In this paper, we propose a our preliminary results to visualize abstract normative systems, in such a way ... [more ▼]

Abstract normative systems allow to reason with norms even when their content is not detailed. In this paper, we propose a our preliminary results to visualize abstract normative systems, in such a way that we are able to reason with institutional facts, obligations and permissions. Moreover, we detect meaningful patterns emerging from the proposed visualization, and we show how these patterns can be used to define commonly used reusable solutions. [less ▲]

Abstract Normative Systems: Semantics and Proof Theory

in PRINCIPLES OF KNOWLEDGE REPRESENTATION AND REASONING: PROCEEDINGS OF THE THIRTEENTH INTERNATIONAL CONFERENCE (2012)

In this paper we introduce an abstract theory of normative reasoning, whose central notion is the generation of obligations, permissions and institutional facts from conditional norms. We present various ... [more ▼]

In this paper we introduce an abstract theory of normative reasoning, whose central notion is the generation of obligations, permissions and institutional facts from conditional norms. We present various semantics and their proof systems. The theory can be used to classify and compare new candidates for standards of normative reasoning, and to explore more elaborate forms of normative reasoning than studied thus far. [less ▲]

Embedding Normative Reasoning into Neural Symbolic Systems

in Proceedings of the Seventh International Workshop on Neural-Symbolic Learning and Reasoning (2011)

Normative systems are dynamic systems because their rules can change over time. Considering this problem, we propose a neural- symbolic approach to provide agents the instru- ments to reason about and ... [more ▼]

Normative systems are dynamic systems because their rules can change over time. Considering this problem, we propose a neural- symbolic approach to provide agents the instru- ments to reason about and learn norms in a dynamic environment. We propose a variant of d’Avila Garcez et al. Con- nectionist Inductive Learning and Logic Program- ming(CILP) System to embed Input/Output logic normative rules into a feed-forward neural network. The resulting system called Normative-CILP(N- CILP) shows how neural networks can cope with some of the underpinnings of normative reasoning: permissions , dilemmas , exceptions and contrary to duty problems. We have applied our approach in a simplified RoboCup environment, using the N-CILP simula- tor that we have developed. In the concluding part of the paper, we provide some of the results ob- tained in the experiments [less ▲]

On the Relationship between I-O Logic and Connectionism

in In Proceedings of the 14th International Workshop on Non-Monotonic Reasoning (NMR'10), Toronto, Canada, May 2010 (2010)