This paper addresses the problem of checking if an updated system is in compliance with the current regulations which apply on the domain. We rst present the applicative context in which this problem has been met. We sketch a formalisation of the problem of compliance and we show that is can be split in several sub-problems of di erent types, the solutions of which are discussed.
{ given a system composed of several components, { given the set of regulations which rule this system, { given a modi cation which is proposed for the system (modi cation concerning its structure or the way of performing its function), { we rst want to be able to check if the modi ed system is in compliance with regulations. If it is not, we want to help users to understand where are the causes of non compliance. Users will then have to revise the given regulations or to revise the proposed modi cation.
This paper is organized as follows. Section 2 tends to formalise the problem of checking compliance of a system with regulations. Section 3 analyses more deeply this problem and shows that it can be split in several sub-problems of di erent types. Section 4 focuses on the problem of providing the users an assistance to revise violated regulations. Section 5 mentions some relevant works, the scienti c domains they belong to (Information Retrieval and Normative Reasoning) being candidate to provide us with solutions. Section 6 concludes this paper. 2
Towards a formalisation of the problem of checking compliance
De nition 1. new denotes the updated system the compliance of which has to be checked.
De nition 2. KB denotes the background knowledge, i.e the knowledge about the considered environment.
Example 1. In the ATS case, if the problem is to check the compliance of the ATS when aircrafts are given a new fuel, then KB may include characteristics and properties of this new fuel (density, volumic mass, in ammation temperature...), but also characteristics of airport environment (atmospheric pressure, physical models...). Any information describing the modi ed ATS when aircrafts are given a new fuel is in new.
>From a more formal point of view, new and KB should be modelled in a common model. For instance, KB could be modelled by ontologies, hierarchy of concepts, dependance graphs between concepts, or more generally, and this will be supposed in the rest of the paper, by logical formulas. In the same way, new could be modelled by sets of nodes in the ontologies, sets of concepts, or more generally, and this will be supposed in the rest of the paper, by logical formulas.
Assumption In the following, we will suppose that new is compatible with KB i.e, KB [ new will be supposed to be a consistent set of formulas.
Consistency is a prerequisite to the problem of compliance since, if KB [ new is inconsistant, this means that new contradicts the domain knowldege, thus, building new is impossible. Consequently, the question of checking his compliance is not posed.
De nition 3. A regulation r is a triplet: r = < str; refr; normsr; defr >, where { str is an ordonned list of the levels which structure the text of r in an arborescent way. { refr denotes the set of other regulations r refers to. { normsr denotes the normative contents of r. If n is in normsr, n is assigned a position label related to str which denotes its position in the arborescent structure of r. { defr is a set of the de nitions of the concepts which are used in the regulation text.
Note that several members of normsr may have the same position label. It means that they are in the same text unit in r.
What we want here to capture is that a regulation contains information of very di erent natures : { conceptual de nition information (defr) : that is an optional part of the regulation. Concepts which are ruled by r are de ned in defr. { rules (normsr) : that is the core of the regulation. The rules apply on the real world by stating what is obligatory, permitted or forbidden under which conditions. Formal modelling rules requires the use of a logical formalism dedicated with normative reasoning i.e a deontic logic (see section 5). In the following, we will thus suppose that these rules are modelled by formulas of such a logic. { In a regulation r, conceptual de nition and rules are expressed according a given structure (str). { information about other regulations refr : regulations which inspire the regulation, regulations which are abrogated by the regulation...One generally mainly nd it in the head of the text of r.
Example 2. For r being [
Several relations exist in R such as: { r2 S r1 is true if regulation r1 is a specialization of regulation r2. S is a partial pre-order de ned upon R. { r2 A r1 is true if regulation r2 abrogates regulation r1 : it means that r1 doesn't apply anymore since r2 applies. A is a partial pre-order de ned upon R. { a binary relation replace so that replace(aij ; akl ) is true if the ith article of regulation rj replaces the kth article of regulation rl.
Some of relations of this type has been presented in [
Example 6. Let r1 and r2 respectively being regulations [
De nition 5. If R = fr1; :::; rng is the set of regulations which apply on the domain, we de ne normsR, as the set of all the rules of all the regulations of R, n i.e, normsR = [i=1normsri normsR is thus a set of formulas of a particular deontic logic.
More formally, we assume that a formal model (formal language and formal inference denoted j= in the following) has been chosen for modelling and reason with rules of normR, background knowledge KB and modi cation new2.
In the rest of the paper, we will suppose that normR is consistent i.e is a
consistent set of rules.3
2 Ideally, this formal model is a logic which allows to express and reason with any
type of deontic notions which appear in regulations, any type of knowledge, causal
or temporal, which appear in KB. Such a logic should then be a deontic logic ([
Checking compliance is then de ned by checking one of the following assertions:
8 j= normsR ! permitted( ) This expresses that all the consequences the system modi cation new (under context KB) are explicitely permitted by the rules in the regulations. In the rst case, new could be accepted without any other modi cation since it is compliant with the regulations.
9 9r 2 R j= normsr ! f orbidden( ) This expresses that the system modi cation, new, has some consequences (under context KB) which are explicitely forbidden by one regulation In this case, new cannot be taken into account since it explicitely leads to violate regulations, unless modifying regulations themselves. Localizing the very rules which are violated by new is addressed in section 4. Notice that in the general case, the prohibition is not caused by only one regulation. So the case of forbidden modi cation should be described by: 9 j= normsR ! f orbidden( ) However, in this paper, we assume that the prohibition is caused by a single regulation because it simpli es the presentation of localizing violated rules (see section 4).
9 This expresses that the system modi cation, new, has some consequences (under context KB) which are neither explicitely permitted nor explicitely forbidden by the regulations. In this case, it will be possible to accept new only after an analyse and modi cations of regulations so that consequences of new are permitted.
By de nition, these three assertions are exhaustive. Furthermore, they are exclusive only if normR is consistent. This is the reason why assuming consistency of rules is a prerequisite to the de nition of compliance.
Decomposing the problem of checking compliance Checking compliance can be decomposed into several sub-problems. The idea is to check compliance only on a subset of R, made of regulations which \apply at present" and \concerned by new". At this step, the property \being a regulation concerned by new" remains to be formally de ned. This property could be de ned so that the test of checking compliance is more e cient in time. It could also be de ned so that we can help the user (in the second case) to nd the precise articles of the regulations that are violated.
{ Problem pb 1 : nd the \regulations which could be violated" This problem can be divised into two sub-problems as follows:
Problem pb 1.1 : nd the \regulations which apply at present" This problem consists in selecting the regulations which are not abrogated nor replaced by other regulations. In other words, the problem is to focus only on the regulations that apply at the moment.
This problem may be de ned by : nd max A (R) 4
n Information in [i=1refri will be hepful to solve this sub-problem . Problem pb 1.2 : nd the \regulations concerned by new" This problem is a problem of Information Retrieval, the information to be retrieved being regulations.
In order to solve it, considering information in [in=1defri (i.e de nitions of the concepts used in the regulation text) will be necessary.
The two above sub-problems may be solved in any sequence order : each of them contributes towards reducing the set of regulations to be considered in checking compliance.
Let us denote Rnew the set of the regulations of R which apply at present and which are concerned by new. { Problem pb 2 : checking compliance of new with Rnew
8 and j= normsr ! f orbidden( ) 9
and 6j= normsRnew ! permitted( ) and 6j= normsRnew ! f orbidden( ) 4 If is a partial pre-order de ned on R, then max (R) is de ned by: max (R) = fr 2 R : 8r0 2 R; r0 r ) r r0g
Towards assisting localization of violated rules In this section, we suppose the case when new doesn't comply with Rnew. I.e, we assume that the second assertion of problem pb 2 is true.
RF orbidden = fr 2 Rnew ; 9
KB[new j= and j= normsr ! f orbidden( )g
RF orbidden denotes the set of regulations which are involved in the cause of non compliance of new with Rnew under KB.
In order to assist users in revising such regulations, several kinds of aids may be proposed to him. Below we sketch some induced problems.
{ Problem pb 3 : localize a cause of non compliance in a regulation Let r 2 RF orbidden. This problem consists in: 1. exhibiting the elements in normsr which are involved in a demonstration of \forbidden modi cation". 2. nding their position label in r (according to str, as de ned in de nition 3). { Problem pb 4 : localize the least specialized regulations involved in non compliance The problem is to identify the uppest regulations involved in non compliance, towards the specialization relation de ned on R : in other words, it is to identify sources (in the specialization or hierarchical sense) of non compliance.
Formally : nd max S (RF orbidden) { Problem pb 5 : propagate a cause of non compliance in a set of regulations The problem is, given a regulation involved in non compliance, to identify all the regulations which specialize it. These regulations, because they take their inspiration from the violated regulations, are are also involved as causes of non compliance.
Formally : let r 2 RF orbidden, nd fr0 2 RF orbidden, r
S r0g.
{ Problem pb 6 : explanation for non compliance The problem is to give
an informative explanation based upon non compliance demonstrations.
This comes to a problem of Explanation Generation, which has been studied
for many years [
Among the di erent sub-problems we have raised in the previous sections, two of them are of particular interest. More speci cally, these are: a problem of information retrieval, the information to be retrieved are regulations (cf problem 1.2) and a problem of normative reasoning (cf problem 2). These two very di erent questions have been addressed by many works we mention some of them below. 5.1
Information Retrieval is a vast domain of research whose works aim to de ne
models and methods or algorithms, to retrieve information among a large set of
information, like the web space. See [
The three most used models in Information Retrieval are the vector space model, the probabilistic model and the inference network model.
According to the vector space model, the user query as well as the documents the query is addressed to, are represented by vectors of terms (words of a given vocabulary for instance). The score of a document is de ned as a similarity degree between its vector and the query vector. Several similarity degrees are usually used, among which the dot product de ned by: if D denotes the document vector and Q denotes the query vector, then the score of D for Q is: sim(D; Q) = n X di:qi i=1 where di is the value of the ith component of (D) and qi is the value of the ith component of (Q). The value di (resp qi) is called the weight of the dith term in the document (resp, query).
Various methods for weighting terms have been de ned. All of them are based on di erent parameters which are : term frequency (words that repeat several times in a text are considered salient), document frequency (words that appear in many documents are considered common and are not very indicative of document content), the number of documents that contain a given term, the document lenght (in bytes), the average document length (in bytes)...
As for Probabilistic models, they assume that documents in a collection should be ranked by decreasing probability of their relevance to a query (probabilistic ranking principle). Since knowing its true value is impossible, the probability of relevance of a document to a query has to be estimated. In this family, the models di er from the way they estimate that probability of relevance.
Last models are Inference network models. In these models, document retrieval is modeled as an inference process in an inference network.
Since we consider Regulation Retrieval as a particular case of Information
Retrieval, solving pb 1.2 could be done by adapting a model of Information
Retrieval. For doing so, the de nitions of concepts used in a regulation (i.e the
defr part) has obviously an important role to play in the process. Furthermore,
the very structure of regulations (i.e the str part) is also something particular
which must be taken into account by Regulation Retrieval models to be de ned
([
Let us also mention [
Let us nally cite [
Problem pb 2 raises the question of checking if a given formula, (here permitted( ) or f orbidden( )), is implied by some rules (here normsRnew ). This is a particular case of what is called \normative reasoning" i.e, reasoning with norms.
Reasoning with norms requires at least modelling deontic notions
(permission, prohibition, obligation...). But it also requires modelling individuals (agents
on which obligations, permission and prohibition apply) and properties on
individuals. It sometimes also require modelling several dimensions of time (time of
validity of norms, deadlines...) and di erent types of norms (defeasible norms,
Contrary-to-duties...). To our knowledge, there is no general logical formalism
which allow to reason with so many di erent notions. However, there are several
kinds of formalisms which allow to model some aspects of the norms. These are
deontic logics [
Most of deontic logics are modal ones, [
However, First Order Logic (FOL) can also been used to reason with deontic
notions ([
Let us nally mention a very theoretical but interesting work, [
In this paper we have addressed the problem of checking compliance of an updated system with regulations. The main contributions are a formalisation of this problem and its decomposition in several sub-problems of di erent types. We also sketched some functionalities which could help a user to revise regulations in case of non compliance. We nally quickly presented relevant litterature, more precisely Information retrieval and Normative Reasoning, which could o er solutions.
Notice however that this work is very preliminary and thus raises many open questions, the most important one being the de nitions of the solutions of the di erent sub-problems and their applicability as well. The case named \case of a non ruled modi cation" has also to be studied. And the model of regulations used in this work, has to be re ned in order to take into account a ner granularity of representation. Indeed, for instance, this model does not allow to represent relations between text units .
However, even preliminary, this work enlights the complexity of the problem of checking compliance and the varieties of questions to be solved.
Acknowledgments. We would like to thank the anonymous reviewers for their comments which helped us to improve the paper.