Salem Benferhat
email: benferhat@cril.fr

Karim Tabia
email: tabia@cril.fr

Amélie Levray
email: alevray@inf.ed.ac.uk

A complexity analysis of MPE inference in possibilistic networks

Keywords: Complexity, Possibilistic networks, MAP inference, MPE inference

Reasoning with uncertainty in graphical models often implies great computational cost. For example, computing the most probable explanation in Bayesian networks is known to be NP PP -complete. Possibilistic networks represent an alternative powerful representation for uncertain information. This paper aims at showing that the computation complexity of MPE inference tasks in possibilistic networks are NP-complete. To that end, we provide full reduction and proof for MPE querying minbased and product-based possibilistic networks. More precisely, we provide incremental proofs based on reductions to and from three well-known NP-complete problems: SAT, 3SAT and Weighted MaxSAT decision problems.

I. INTRODUCTION

Beliefs graphical models, such as Bayesian networks [START_REF] Darwiche | Modeling and Reasoning with Bayesian Networks[END_REF], credal networks [START_REF] Cozman | Credal networks[END_REF], or possibilistic networks [START_REF] Borgelt | Possibilistic graphical models[END_REF] are powerful means of compactly represent uncertainty using directed acyclic graphs and independence relationships. Typically, possibilistic networks are seen as counterparts of Bayesian networks based on possibility theory [START_REF] Dubois | Possibility theory and statistical reasoning[END_REF], where possibility degrees are more suited for handling imperfect, qualitative and partial information.

Inference in such graphical models has been extensively studied and many algorithms have emerged. On the other hand, while complexity results regarding inference in probabilistic networks are well-established [START_REF] Darwiche | Complexity results and approximation strategies for MAP explanations[END_REF]- [START_REF] Cassio | The inferential complexity of bayesian and credal networks[END_REF], there is no such deep study for possibilistic networks. This paper aims at filling this gap.

Essentially, in graphical models there are three common types of queries: computing most probable (or plausible) explanation (MPE); computing a posteriori probability (or possibility) degrees (Pr); and computing the maximum a posteriori explanation (MAP ). These tasks are known to be very hard in the probabilistic setting. Indeed, the decision problems associated to MPE, Pr, MAP are NP-complete, PP -complete and NP PP -complete respectively (see [START_REF] Darwiche | Complexity results and approximation strategies for MAP explanations[END_REF], [START_REF] Cassio | The inferential complexity of bayesian and credal networks[END_REF] for more details on complexity issues in Bayesian and credal networks). In this paper, we focus on possibility theory where we consider two interpretations of possibility theory, minbased possibility theory and product-based possibility theory [START_REF] Dubois | Possibility Theory: Qualitative and Quantitative Aspects[END_REF].

In [START_REF] Benferhat | Possibilistic networks: MAP query and computational analysis[END_REF], the authors analysed the computational complexity of MAP queries in min-based and product-based possibilistic networks. They showed that the decision problem behind MAP querying is NP-complete for both min-based and productbased possibilistic networks. Regarding MAP querying a product-based possibilistic network, only the proof of NPhardness has been provided. The first part of this paper provides the proof of NP-completeness theorem, stated in [START_REF] Benferhat | Possibilistic networks: MAP query and computational analysis[END_REF], of MAP querying a product-based possibilistic network. In the second part of the paper, we address the complete analysis of the decision problems associated with the most plausible explanation (MPE) task in both min-based and product-based possibilistic networks, show using a reduction to the SAT decision problem, that it is NP-complete. Such computational complexity outcomes favour possibility theory as an efficient alternative for reasoning with uncertainty (some results on learning possibilistic parameters over probabilistic ones can be found in [START_REF] Haddad | Learning the parameters of possibilistic networks from data: Empirical comparison[END_REF]).

The paper is outlined as follows. In section II, we briefly recall notions on possibility theory, as well as give motivations. The third section investigates general properties on inference tasks in possibilistic networks. In particular, we provide the proof that the decision problem based on conditioning operator is the same as the one based on conjunction operator when computing MAP queries. Hence, we no longer need conditioning rule in the computation of MAP queries. The fourth section addresses the NP-completeness result of MAP inference in product-based possibilistic networks. In the fifth section, we establish the complexity of MPE inference. This is done by showing a reduction from 3SAT to MPE querying a binary and boolean possibilistic networks, and conversely with a reduction from MPE in a possibilistic network to a SAT problem.

II. A REFRESHER ON POSSIBILITY THEORY AND POSSIBILISTIC NETWORKS

In this section, we give a short reminder of the basic notions associated to possibility theory [START_REF] Dubois | Possibility Theory: Qualitative and Quantitative Aspects[END_REF] and its associated graphical models named possibilistic networks [START_REF] Ben Amor | Preference modeling with possibilistic networks and symbolic weights: A theoretical study[END_REF], [START_REF] Borgelt | Graphical models -methods for data analysis and mining[END_REF], [START_REF] Garcia | Complexity results and algorithms for possibilistic influence diagrams[END_REF]. A possibility distribution, denoted by ⇡, is a mapping from the set of possible worlds ⌦ to the unit interval [0, 1]. Note that we consider a finite and discrete set. For a given interpretation ! 2 ⌦, ⇡(!) = 1 is interpreted as fully possible. ⇡(!) = 0 is interpreted as impossible. ⇡ is said to be normalised if there is at least an element ! 2 ⌦ that is fully possible (i.e. such

(Preprint version)

that ⇡(!) = 1).

There are two understandings of the scale [0, 1] of possibility degrees, either the product-based interpretation as in probability theory or the min-based interpretation which considers degrees on an ordinal scale. These two interpretations lead to two different conditioning rules when dealing with new evidence. We call min-based conditioning | m the operation leading to ⇡(.| m ) given by [START_REF] Dubois | Possibility Theory: Qualitative and Quantitative Aspects[END_REF], [START_REF] Hisdal | Conditional possibilities independence and non interaction[END_REF]:

⇡(! i | m ) = 8 <
:

1 if ⇡(! i ) = ⇧( ) and ! i 2 ; ⇡(! i ) if ⇡(! i ) < ⇧( ) and ! i 2 ; 0 otherwise. (1)
The product-based conditioning, denoted by | ⇤ , is, as in the probabilistic setting, defined as follows:

⇡(! i | ⇤ ) = 8 < : ⇡(! i ) ⇧( ) if ! i 2 ; 0 otherwise. (2)
A possibilistic network denoted PN =< G, ⇥ > is specified by two components:

• A graphical component G: a directed acyclic graph (DAG) where each node represents a discrete variable and edges encode independence relations between variables.

• A numerical component ⇥: a set of local normalised possibility distributions ⇥ i = ⇡ PN (X i |par(X i )) of each node X
i given its parents par(X i ). The joint possibility distribution is factorised using a chain rule, defined as: It is well-known that inference in probabilistic models is a hard task in the general case. In particular, the decision problem associated with MAP in Bayesian networks is NP PPcomplete [START_REF] Darwiche | Complexity results and approximation strategies for MAP explanations[END_REF]. The next sections address the same complexity issues on product-based possibilistic networks as well as the computational complexity of MPE inference.

⇡ PN ⌦ (X 1 , .., X n ) = ⌦ i=1,..,n ⇡ PN ⌦ (X i | ⌦ par(X i )). (3
The complexity of MAP querying a min-based possibilistic network has already been discussed in [START_REF] Benferhat | Possibilistic networks: MAP query and computational analysis[END_REF] and it has been shown that MAP inference in this context is NP-complete.

But first, we recall the definition of inference tasks in possibilistic networks.

III. INFERENCE IN POSSIBILISTIC NETWORKS

In this paper, we investigate two of the most common types of queries when reasoning with graphical models, that are MAP inference and MPE inference. MAP queries require searching for the most plausible instantiation of query variables Q given an evidence e (an instantiation of a set of variables E). While MPE queries search for the most plausible explanation of an evidence e. More formally, MAP query: Let PN be a possibilistic network over the set of variables V , Q ⇢ V be a set of query variables and E ⇢ V be a set of evidence variables with Q \ E = ;. Then, given an evidence E = e, the aim is to compute the most plausible instantiation q of Q given the evidence e.

MPE query: Let PN be a possibilistic network over the set of variables V , E ⇢ V be a set of evidence variables. We denote X the set of remaining variables (X = V \ E). Then, given an evidence E = e, MPE query compute the most plausible instantiation x of X compatible with the evidence e. Stated otherwise by:

argmax x2X (⇧ PN (x, e)). (5)
Note that ⇧ PN (x, e) is the possibility degree of the conjunction of x and e, especially since X \ E = ;. Another notation commonly used is ⇧ PN (x ^e).

In [START_REF] Benferhat | Possibilistic networks: MAP query and computational analysis[END_REF], it is stated that in the case of a MAP query, the problem can be reduced to finding the most plausible assignment of query variables Q compatible with the evidence e. More precisely, it can be rewritten as:

argmax q2DQ (⇧ PN (q, e)). (6)
Namely, given a possibilistic network PN , Q the set of query variables and an evidence e (an instantiation of variables E), we have:

argmax q2DQ (⇧ PN (q|e)) = argmax q2DQ (⇧ PN (q, e)). (7
) Simply put, the conditioning rule of possibility theory is not required to compute the maximum a posteriori assignment. In this section, we provide the full proof of Equation (7) of the above statement, stated in [START_REF] Benferhat | Possibilistic networks: MAP query and computational analysis[END_REF].

• Let us start with the min-based conditioning. Given a possibilistic network PN m over V and let Q and E be two subsets of V (s.t. Q \ E = ;). Then, computing argmax q2DQ (⇧(q|e)) is equivalent to searching the instantiation q such that ⇧(q|e) = 1. By definition of the min-based conditioning, ⇧(q|e) = 1 if ⇧(q, e) = ⇧(e). Assume that argmax q2DQ (⇧(q, e)) is q 0 then since ⇧(e) = max !✏e ⇡(!) or said otherwise ⇧(e) = max q2DQ ⇧(q, e) which is given by ⇧(q 0 , e). • Let us now consider product-based conditioning. In the same way, since the possibilistic network PN ⇤ is normalised then 8e 2 E, argmax q2DQ (⇧(q|e)) is equivalent to searching the instantiation q such that ⇧(q|e) = 1. Which, by definition, is given by ⇧(q|e) = ⇧(q, e) ⇧(e) , therefore, ⇧(q|e) = 1 if ⇧(q, e) = ⇧(e).

From there, assume that argmax q2DQ (⇧(q, e)) is q 0 then since ⇧(e) = max !✏e ⇡(!) = ⇧(q 0 , e). Thus, argmax q2DQ (⇧ PN (q|e)) = argmax q2DQ (⇧ PN (q, e)). Given this equivalence, we can focus only on the MAP problem redefined by Equation [START_REF] Darwiche | Modeling and Reasoning with Bayesian Networks[END_REF].

IV. MAP QUERYING PRODUCT-BASED POSSIBILISTIC

NETWORKS

In [START_REF] Benferhat | Possibilistic networks: MAP query and computational analysis[END_REF] a computational complexity analysis of MAP queries in min-based and product-based possibilistic networks is provided. In particular, it is stated that the decision problem behind MAP querying is NP-complete for product-based possibilistic networks. The full proof of NP-hardness has been provided. This section provides the proof of NP-completeness theorem, stated in [START_REF] Benferhat | Possibilistic networks: MAP query and computational analysis[END_REF], of MAP querying a product-based possibilistic network. Let us first give a brief refresher on decision problems associated with MAP querying productbased possibilistic networks.

A. Definition of the decision problems

Let us recall the definition of the decision problem associated with a MAP query in product-based possibilistic networks, denoted ⇡ ⇤ -D-MAP. Definition 1. By ⇡ ⇤ -D-MAP(PN ⇤ , Q, e, t) we denote the decision problem associated with MAP querying possibilistic networks that we define by: Input:

• PN ⇤ : a product-based possibilistic network • e (evidence): an instantiation of a set of variables E • Q (query): a set of variables with Q \ E = ; • t: a real number in (0, 1].
Question: Is there an instantiation q of non observed variables

Q such that ⇧ PN ⌦ (q, e) t?
As said before, the decision problem we refer to in this reduction is the weighted MaxSAT problem. It is defined as follows:

Definition 2. By D-WMaxSAT( , k) we denote the decision problem specified by: Input:

• : a weighted CNF formula over boolean variables V = {X 1 , ..., X n } simply represented by

= 8 > > < > > : (C 1 , ↵ 1 ), (C 2 , ↵ 2 ), ... (C m , ↵ m ). 9 > > = > > ;
where C 0 i s are clauses and ↵ 0 i s are positive integers. Let Q be a subset of V , e = e 1 , ..., e l be an instantiation of evidence variables E (with Q \ E = ;) and t be a threshold. Then PN ⇤ ,Q,e,t is defined by: R [ 0 [ e where

R = {(¬x i _ ¬u ij , ↵ i ) : ⇡ PN ⇤ (x i |u ij ) = 2 ↵i }, 0 = {(¬x i _ ¬u ij , M) : ⇡ PN ⇤ (x i |u ij ) = 0}, e = {(e k , M) : k = 1, ..., l}, (8)
where

M > P {↵ i : (¬x i _ ¬u ij , ↵ i ) 2 R }. Example 1 illustrates Definition 3.
Example 1. Let us consider the product-based possibilistic network PN ⇤ of Figure 1. Let Q = {B} be a subset of V , let e = ¬c be an instantiation of evidence variables E = {C} and let t = 2 2 be the threshold. Let M = 30. Then following Definition 3, the weighted CNF formula PN ⇤ ,{B},¬c,2 2 is

A B C A ⇡ PN ⇤ (A) a 1 ¬a 2 4 B ⇡ PN ⇤ (B) b 2 8 ¬b 1 C A B ⇡ PN ⇤ (C|AB) c a b 2 7 ¬c a b 1 c a ¬b 1 ¬c a ¬b
PN ⇤ ,{B},¬c,2 2 = 8 > > > > > > > > < > > > > > > > > :
(a, 4), (¬b, 8), (¬c _ ¬a _ ¬b, 7), (c _ ¬a _ b, 2),

9 > > = > > ; R (¬c _ a _ b, 30), (¬c _ a _ ¬b, 30), 0 (¬c, 30) e 9 > > > > > > > > = > > > > > > > > ;
2) Reduction from a product-based possibilistic network to a weighted CNF formula: Theorem 1, given in [START_REF] Benferhat | Possibilistic networks: MAP query and computational analysis[END_REF], provides the result that the decision problem ⇡ ⇤ -D-MAP(PN ⇤ , Q, e, t) can be reduced into D-WMaxSAT ( PN ⇤ ,Q,e,t , k). Theorem 1. [START_REF] Benferhat | Possibilistic networks: MAP query and computational analysis[END_REF] Let PN ⇤ be a product-based possibilistic network. Let Q be a subset of V , e be an instantiation of variables E and t be a threshold. Let PN ⇤ ,Q,e,t be the CNF formula given by Definition 3. Then, ⇡ ⇤ -D-MAP(PN ⇤ , Q, e, t) answers "yes" if and only if D-WMaxSAT( PN ⇤ ,Q,e,t , X + log 2 t + M ⇤ (Z + |E|)) answers "yes" where ⇡ ⇤ -D-MAP is given by Definition 4 and D-WMaxSAT is given by Definition 2.

In this section, we provide the full proof of Theorem 1 and illustrate it with examples.

Proof. Let us first define the parameters of the WMaxSAT decision problem, D-WMaxSAT( PN ⇤ ,Q,e,t , k). Namely,

• PN ⇤ ,Q,e,t is the weighted CNF formula given by Definition 3.

• k is the threshold for the problem and it is given by:

k = X + log 2 t + M ⇤ (( X ⇧ PN ⇤ (x i |u i ) = 0) + 1) (9)
where M is defined in Definition 3. And X is given by the sum of weights in R : X =

P {↵ i : (¬x i _ ¬u ij , ↵ i ) 2 R } .
The second part of the proof consists in showing that the two decision problems as defined are equivalent. Let the query associated to D-WMaxSAT be: Does D-WMaxSAT( PN ⇤ ,Q,e,t , X + log 2 t + M ⇤ (Z + 1)) answer "yes"? More precisely, is there an instantiation of all variables that satisfies a subset of clauses in PN ⇤ ,Q,e,t having the sum of the degrees of the satisfied clauses greater or equal to k?

Recall that ⇡ ⇤ -D-MAP decision problem is: Given an instantiation e of evidence variables, is there an instantiation q of query variables Q such that ⇧(q, e) t?

For the sake of clarity, in this proof we simply write instead of PN ⇤ ,Q,e,t .

? Assume that D-WMaxSAT( , k) answers "yes". This means that there exists a subset A ✓ such that:

• {( i , ↵ i ) 2 A} is consistent and • P ( i ,↵i)2A ↵ i k Note that we can state that {(e k , M) : k = 1, ..., l} is included in A. Indeed, if some ( i , M) of is not in A then P ( i ,↵i)2A cannot be greater than M ⇤ (Z + |E|). Let us denote by A ⇤ = A \ {( i , M) : ( i , M
) 2 A} then we can also state that:

• {( i , ↵ i ) 2 A ⇤ } is consistent, • P ( i ,↵i)2A ⇤ ↵ i X + log 2 t Let ! be a model of { i : ( i , ↵ i ) 2 A} and { i : ( i , ↵ i ) 2 A ⇤ }. Since X = P {↵ i : ( i , ↵ i ) 2
and ↵ i 6 = M }. Then the latter equation implies that:

X {↵ i : ( i , ↵ i ) 6 2 A ⇤ }  log 2 t
This can be rewritten as:

X {↵ i : ( i , ↵ i ) 2 \ A, ! 2 i }  log 2 t
It is enough now to consider the following immediate simplified inequalities to get the desirable result.

P {↵ i : ( i , ↵ i ) 2 \ A, ! 2 i }  log 2 t P {log 2 2 ↵i : ( i , ↵ i ) 2 \ A, ! 2 i }  log 2 t log 2 (⇤{2 ↵i : ( i , ↵ i ) 2 \ A, ! 2 i })  log 2 t log 2 (⇤{2 ↵i : ! 2 ¬x i _ ¬u ij })  log 2 t log 2 (⇤{2 ↵i : ! ✏ x i ^uij })  log 2 t log 2 ⇡ PN ⇤ (!)  log 2 t ⇡ PN ⇤ (!) t with ! ✏ e.
Hence the answer to ⇡ ⇤ -D-MAP(PN ⇤ , Q, e, t) is also "yes" by taking q such that ! |= q.

? Assume that D-WMaxSAT( PN ⇤ ,Q,e,t , k) answers "no". Then, for all consistent subset of clauses A that include 0 and e we have

X {↵ i : ( i , ↵ i ) 2 A} < k.
Let us consider such a subset A ⇤ . Let ! be a model of A ⇤ , then following the same previous steps we have:

P {↵ i : ( i , ↵ i ) 2 \ A ⇤ s.t ! 2 i } > log 2 t log 2 (⇤{2 ↵i : ! 2 ¬x i _ ¬u ij }) > log 2 t log 2 (⇤{2 ↵i : ! ✏ x i ^uij }) > log 2 t log 2 ⇡ PN ⇤ (!) > log 2 t ⇡ PN ⇤ (!)
< t with ! ✏ e. Hence the answer to ⇡ ⇤ -D-MAP(PN ⇤ , Q, e, t) is also "no".

Example 2. Let Q = {B} and E = {C} be the set of query variables and evidence variables respectively. Let us consider the evidence e = ¬c. Let PN ⇤ ,Q,e,t be the weighted CNF formula associated to PN ⇤ given by Definition 3. The MAP query over PN ⇤ is: Is there an instantiation q of the variables

Q such that ⇧ PN ⇤ (q, e) 2 2
. Hence, the corresponding problem D-WMaxSAT( PN ⇤ ,Q,e,t , k) is given by: Is there an instantiation of the variables such that the sum of the degrees of the satisfied clauses is greater or equal to k?

Let us set the values of the variables X, M and Z: X = 21, M = 30, and Z = 2. Then, k = X+log 2 t+30⇤(Z+1) = 109. Given this configuration, D-WMaxSAT( PN ⇤,{B},¬c,2 2 , 109) answers "yes". Indeed, it is enough to consider A such that

A = 8 > > > > > > < > > > > > > :
(a, 4), (¬b, 8), (¬c _ ¬a _ ¬b, 7), (¬c _ a _ b, 30), (¬c _ a _ ¬b, 30), (¬c, 30)

9 > > > > > > = > > > > > > ;
The sum of the weights in A is equal to 109. A model of formulas in A can be a¬b¬c for which using the productbased chain rule has a possibility degree of ⇧ PN ⇤ (a¬bc) = 2 2 . Hence, ⇡ ⇤ -D-MAP(PN ⇤ , {B}, ¬c, 2 2 ) answers "yes" as well.

C. Complexity of MPE inference

In this subsection, we analyse the complexity of MPE inference in product-based possibilistic networks. As we have mentioned in the definition of the query, we search for the assignment of all variables compatible with the evidence. Which means that the only difference with a MAP query as redefined in Equation ( 6) is that instead of a subset of variables we use all of them.

Based on what has just been proven for MAP inference, we argue that by choosing a set of query variables corresponding to the remaining variables V \E, the complexity results follows from Theorem 1. This is formally stated in the following proposition.

Proposition 1. ⇡ ⇤ -D-MPE is NP-complete.
We provide a more rigorous proof for MPE inference in min-based possibilistic networks in the next section.

V. COMPLEXITY ANALYSIS OF MPE INFERENCE IN

min-BASED POSSIBILISTIC NETWORKS This section focuses on MPE query in min-based possibilistic networks. Contrary to MAP inference, where the complexity analysis have shown that MAP inference in possibilistic networks costs less than in Bayesian networks; Here we show that MPE querying a possibilistic network is NP-complete as in Bayesian networks.

Basically, to prove that ⇡ m -D-MPE is NP-complete, we follow the same steps as in the analysis of MAP in min-based possibilistic networks given in [START_REF] Benferhat | Possibilistic networks: MAP query and computational analysis[END_REF]. More precisely,

• we first show the NP-hardness of ⇡ m -D-MPE by providing a reduction from the D-3SAT decision problem to ⇡ m -D-MPE decision problem. In particular, in this reduction we build a special possibilistic network that only takes into account boolean variables and binary values. This network is called a binary and boolean possibilistic network (see [START_REF] Benferhat | Possibilistic networks: MAP query and computational analysis[END_REF] for more details).

• we provide a reduction of the ⇡ m -D-MPE decision problem, defined for min-based possibilistic networks, to the D-SAT decision problem.

A. Definition of the decision problems

We first formally define the decision problem associated with a MPE query in min-based possibilistic networks, denoted ⇡ m -D-MPE as well as the decision problem associated with querying a B&B possibilistic network. In [START_REF] Benferhat | Possibilistic networks: MAP query and computational analysis[END_REF], the authors gave the reasons why we can afford to only consider the case ⇧ PN B&Bm (x, e) = 1.

Let us now recall the boolean satisfiability decision problem denoted D-SAT. Definition 6. By D-SAT( ) we denote the decision problem associated to determining if there exists an assignment ! that satisfies . It is defined by: Input: a formula in a conjunctive normal form Question: Is satisfiable?

A restricted version of the SAT problem involves a 3CNF and is called D-3SAT decision problem. A 3CNF is a formula in a conjunctive normal form for which each clause is a disjunction of at most 3 literals. Thus, Definition 7. By D-3SAT( ) we denote the decision problem defined by: Input: a 3CNF formula Question: Is satisfiable?

B. From 3SAT to MPE querying over B&B possibilistic networks

As in [START_REF] Benferhat | Possibilistic networks: MAP query and computational analysis[END_REF], we build a B&B possibilistic network from a 3CNF. The definition of this reduction is recalled by Definition 8. For more details, the reader can refer to [START_REF] Benferhat | Possibilistic networks: MAP query and computational analysis[END_REF].

Definition 8. Let = C 1 ^C2 ^... ^Cm be a 3CNF formula. Let V = {X 1 , ..., X
n } be the set of propositional variables appearing in . The B&B possibilistic network associated with , denoted by PN is defined as follows:

1) For each propositional symbol X i appearing in , we add a boolean node variable in the graph. Each variable

X

i is associated with a possibility distribution given by: ⇡ PN (x i ) = 1 and ⇡ PN (¬x i ) = 1. 2) For each clause C j of , we add a conditional node variable, C j . Parents of C j are the rooted variables X i that are involved in C j . Each C j is associated with a conditional possibility distribution given by: 8u jk an instance of parents of C j that models the satisfiability of the clause.

C. From querying min-based possibilistic networks to SAT

In this section, we no longer restrict ourselves to binary possibility distributions. Namely, (conditional) possibility degrees can take any value in the unit interval [0, 1]. However, for the sake of simplicity, we still only consider boolean variables. This is not a restriction and the proof can be adapted by encoding a non-boolean variable by a set of boolean variables. We propose to reduce the decision problem ⇡ m -D-MPE to the decision problem D-SAT.

The following gives the definition of the CNF formula associated with the network a MPE query, denoted by PN m,e,t . Definition 9. Let PN m be a min-based possibilistic network over the set of boolean variables V = {X 1 , ..., X n }. Let e = e 1 , ..., e l be an instantiation of evidence variables E and let t be a threshold. Then PN m,e,t over the set of variables V = {X 1 , ..., X n }, is given by:

PN m,e,t = {(¬x i _ ¬u ij ) : ⇡ PN m (x i |u ij ) < t} [ {e k : k = 1, ..., l}
This reduction is done in polynomial time (and space) with respect to the size of PN m .

The following theorem states that ⇡ m -D-MPE can be reduced to D-SAT. Theorem 3. Let PN m be a min-based possibilistic network, e be an instantiation of evidence variables E and t be a real number in (0, 1]. Let P Nm,e,t be the CNF formula given by Definition 9. Then, ⇡ m -D-MPE(PN m , e, t) says "yes" if and only if D-SAT( PN m ,e,t ) says "yes" where ⇡ m -D-MPE is given by Definition 4 and D-SAT is given by Definition 6.

Proof. The proof is similar to the one provided in [START_REF] Benferhat | Possibilistic networks: MAP query and computational analysis[END_REF] for analyzing the complexity of map-querying possibilistic networks. We need to prove that when PN m,e,t is satisfiable then ⇧ PN m (x, e) t and that when PN m ,e,t is unsatisfiable then ⇧ PN m (x, e) < t for all assignments of all variables compatible with e. To summarise Proposition 1 together with Theorems 2 and 3 show that the decision problem associated with MPE inference is NP-complete for both min-based and productbased possibilistic networks.

VI. CONCLUSIONS

This paper dealt with the computational complexity of inference in possibilistic networks. The main results shown in this work proved that possibilistic networks offer interesting advantages for reasoning with uncertain information. These results have an impact on the complexity of reasoning in the interval-based possibilistic setting. A future work concerns the computation of the a posteriori possibility degree of an event in both min-based and product-based possibilistic networks.

  ) where ⌦ = m in min-based possibilistic setting and ⌦ = ⇤ in product-based possibilistic setting.

  argmaxq2DQ (⇧ PN (q|e)).

  • k: a positive integer Question: Is there an instantiation of variables V such that the sum of weights of satisfied clauses in is greater or equal to k? B. From querying product-based possibilistic networks to WMaxSAT 1) Definition of a weighted CNF formula associated to a product-based possibilistic network: In what follows, we will reuse the same weighted CNF formula associated to a productbased possibilistic network and defined in [2]. Definition 3. Let PN ⇤ be a product-based possibilistic network over the set of boolean variables V = {X 1 , ..., X n }.

1 Fig. 1 .

 11 Fig. 1. Example of a product-based possibilistic network PN ⇤ over A, B and C.

Definition 4 .

 4 We denote ⇡ m -D-MPE(PN m , e, t) the decision problem associated with MPE querying a min-based possibilistic network. It is defined by: Input:• PN m : a min-based possibilistic network • e (evidence): an instantiation of a set of variables E • t: a real number in (0, 1]. Question: Is there an instantiation x of the variables X such that ⇧ PN m (x, e) t? Definition 5 considers a particular case of Definition 4 where degrees are either 0 or 1 (hence no need to explicitly specify t). Definition 5. By B&B m -D-MPE(PN B&Bm , e) we denote the decision problem associated with MPE querying a min-based Boolean and Binary possibilistic network that we define by: Input: • PN B&Bm : a min-based binary and boolean possibilistic network over V = {X 1 , ..., X n } • e (evidence): an instantiation of a set of observation variables E Question: Is there an instantiation x of variables X such that ⇧ PN B&Bm (x, e) = 1?

3 )

 3 Lastly, we add a single boolean node, E , which represents the satisfiability of the overall formula . It has all nodes C 0 j s as parents. Intuitively, E is set to true if all clauses are satisfied.

	Theorem 2 provides the reduction from the decision prob-
	lem D-3SAT( ) into B&B	m -D-MPE(PN , e) where the in-
	put e is let to e . More formally:
	Theorem 2. Let B&B possibilistic network given by Definition 8. Let V PN be a 3CNF formula. Let PN be the be the set of variables in PN , namely {X 1 , ..., X n } [ {C 1 , ..., C m } [ {E }. Then, D-3SAT( ) answer is "yes" if and only if the B&B m -D-MPE(PN , e ) answers "yes" where D-3SAT is given in Definition 7 and B&B

m -D-MPE is given by Definition 5.

•

  Assume that PN m,e,t is satisfiable. This means that there exists an instantiation of all variables, denoted by ! ⇤ , that satisfies all clauses of PN m,e,t including e = e 1 , ..., e l . Then we have ⇡ PN m (x i |u ij ) < t by construction of PN m,e,t . So if ! ⇤ satisfies all clauses in PN m,e,t then ! ⇤ falsifies each of the formulas in {(x i ^uij ) : (¬x i _ ¬u ij ) 2 PN m,e,t }. Thus, all conditionals ⇡ PN m (x i |u ij ) applied in chain rule to compute ⇡ PN m (! ⇤ ) have a possibility degree greater or equal to t. Therefore, ⇡ PN m (! ⇤ ) t. Hence the answer to ⇡ m -D-MPE(PN m , e, t) is also "yes". • Assume that PN m ,e,t is unsatisfiable. Then for all instantiation of variables ! such that ! |= e(= e 1 ^..^e l ), there exists at least a clause C i = ¬x i _ ¬u ij that is falsified by ! (and hence ! |= x i ^uij ). And by construction of PN m,e,t , we have ⇡ PN m (x i |u ij ) < t, so using the min-based chain rule we have 8! |= e, ⇡ PN m (!) < t. Hence ⇡ m -D-MPE(PN m , e, t) is also "no".

VII. ACKNOWLEDGEMENTS

This work is supported by the european project H2020 Marie Sklodowska-Curie Actions (MSCA) research and Innovation Staff Exchange (RISE): AniAge (High Dimensional Heterogeneous Data based Animation Techniques for Southeast Asian Intangible Cultural Heritage).


Hamadjam Abboubakar
email: h.abboubakar@gmail.com

Raissa Kom

Rubin Fandio

H P Ekobena Fouda

Fractional modeling of Hansen's disease (Leprosy) transmission dynamics

Keywords: Hansen's disease (Leprosy), Fractional derivative, Caputo derivative, Asymptotic stability, Fixed point theory

In this work, we study a mathematical model for the Hansen's disease (leprosy) transmission dynamics with both integer and fractional derivatives in the Caputo sense. After the model formulation, we compute the leprosy reproduction number R 0 and prove the existence of two steady states named the Leprosy-free equilibrium and the leprosy-endemic equilibrium which exists and is unique if and only if R 0 > 1. Using the general theory of Lyapunov, we prove the global asymptotic stability of both steady states, for both models. The existence and uniqueness of the solutions of the fractional model are proved using fixed point theory. We finally perform numerical simulations to validate our analytical results, as well as to evaluate the impact of varying the fractional-order parameter on the disease dynamics.

I INTRODUCTION

Hansen's disease, previously known colloquially as Leprosy, is a contagious disease that affects the skin, mucous membranes, and nerves, causing discoloration and lumps on the skin and, in severe cases, disfigurement and deformities. Hansen's disease is now mainly confined to tropical Africa and Asia [START_REF] Sasaki | Mycobacterium leprae and leprosy: a compendium[END_REF]. In 2019, Hansen's disease has reported by 153 countries to the World Health Organization (WHO) among which 24 were from the Western Pacific region, 19 from the Eastern Mediterranean region, 31 from the region of the Americas, 11 from the South-East Asia region, 30 from the European region, and 38 from the African region [START_REF]al. Global leprosy update, 2018: moving towards a leprosy-free world-situation de la lèpre dans le monde, 2018: parvenir à un monde exempt de lèpre[END_REF].

Several model was developed to study the spread of Hansen's disease. To investigate the impact of relapse cases and non-compliance with WHO multi-drug therapy among leprosy patients, Mushayabasa et al. in [START_REF] Mushayabasa | Understanding noncompliance with who multidrug therapy among leprosy patients: insights from a mathematical model[END_REF] formulated a compartmental model. They computed the basic reproduction number and prove global stability of the steady states. Based on the understanding of the biology of the infection, Smith et al. [START_REF] Lee | Proposing a compartmental model for leprosy and parameterizing using regional incidence in brazil[END_REF] proposed a compartmental model for Hansen's disease dynamics. After computed the basic reproduction number, She fitted the transmission coefficients for the model and the rate of detection using real data of Hansen's disease in 5 regions of Brazil. In [START_REF] Edward T Chiyaka | Theoretical assessment of the transmission dynamics of leprosy[END_REF], Chiyaka et al. investigate non-compliant behavior by patients on treatment and possible inadequacy of the prescribed treatments as the reason for the persistence of the disease in the Sub-Saharan Africa region. To this aim, they construct compartmental mathematical models of the transmission dynamics of Hansen's disease, which are modified to encapsulate non-compliance and inadequate treatment. In order to predict the transmission of new patients and allow different groups of individuals to be analyzed in the face of exposure and infection, Dias et al. in [START_REF] Dias | Mathematical and computational and modeling for leprosy's dynamics[END_REF] studied a compartmental model which illustrates the dispersion of leprosy in a population, seeking the impact on the understanding of transmission and planning of disease control strategies. To control the infection, Haroun et al. [START_REF] Mo Haroun | Clinical characteristics of neuropathic pain in leprosy and associated somatosensory profiles: a deep phenotyping study in india[END_REF] studied the benefits of multi-drug therapy as a control measure. In this paper, we extend the recent work of Raza & Rafiq [START_REF] Raza | Modeling and transmission dynamics of leprosy disease: Via numerical methods[END_REF] by replacing: (1) mass action incidence by standard incidences; (2) integer derivative by fractional derivative in the Caputo's sense. After the formulation of the news models (with integer and fractional derivative), we compute the new basic reproduction number R 0 as well as the steady states ( the leprosy-free equilibrium and the unique endemic equilibrium). We prove the global asymptotic stability of these steady states depending on the value of R 0 , using Lyapunov theory and LaSalle invariance principle [START_REF] Joseph | The stability of dynamical systems[END_REF]. The existence and uniqueness of solutions of the fractional model are also proved. Through the Adams-Bashforth-Moulton method. we construct a numerical scheme for the fractional model. Finally, several simulations are performed to validate our analytical results, as well as to see the impact of varying the fractional parameter on the disease spread.

The paper is organized as follows: In Section II, we present the definition of the Caputo operator, as well as two results required for model analysis. The new leprosy models are formulated in Section III, as well as the existence and stability analysis of steady states, the existence, and uniqueness of solutions of the fractional model. Numerical simulation results, are presented in Section IV. A conclusion round up the paper.

II PRELIMINARIES

Before formulating and studying the fractional model of Hansen's disease (Leprosy) transmission dynamics, we first present a definition of the Caputo operator, as well as two results required for model analysis (see [START_REF] Li | The finite difference methods for fractional ordinary differential equations[END_REF]).

Definition 1: Let f ∈ C l [0; a], a > 0, η ∈ R, l ∈ N such that l -1 < η < l.
The fractional derivative in the Caputo sense of order l, of f is given by

C D η t f (t) = d l f (t) dt l , η = l ∈ N 1 Γ(l-η) t 0 (t -φ) l-η-1 f (l) (φ) dφ, l -1 < η < l , l ∈ N. (1)
Lemma 1: If 0 < η < 1 and d ∈ N, then we can find nonnegative constants W η,1 and W η,2 only dependent on η, such that

(d + 1) η -d η ≤ W η,1 (d + 1) η-1 and (d + 2) η+1 -2(d + 1) η+1 + d η+1 ≤ W η,2 (d + 1) η-1 .
Lemma 2: Assume that x q,i = (i -q) η-1 (q = 1, 2, ..., i -

1) & x q,i = 0 for q ≥ i, η, Q, h, Y > 0, kh ≤ Y & k ∈ N. Let q=i q=k x q,i |e q | = 0 for k > i ≥ 1. If |e i | ≤ Qh η i-1 q=1 x q,i |e q | + |η 0 |, i = 1, 2, ..., k,, then |e k | ≤ W |η 0 |, k = 1, 2, ...,
, where W ∈ R + is independent of k and h.

III MODEL FORMULATION AND BASICS RESULTS

The proposed model, which is a extension of the model proposed by Raza & Rafiq [START_REF] Raza | Modeling and transmission dynamics of leprosy disease: Via numerical methods[END_REF], is presented as follows:

               D t x(t) = p - (β m z + β ρ w) x x + y + z + w -µx, D t y(t) = (β m z + β ρ w) x x + y + z + w -θy -µy, D t z(t) = f θy -µz, D t w(t) = θ(1 -f )y -µw.
(

) 2
In model ( 2), D t denotes the integer derivative with respect to time t; p is the annual recruitment rate; µ is the death rate; β m is the Effective contact rate by multibacillary leprosy; β ρ is the effective contact rate for paucibacillary leprosy; θ denotes the transmission rate of asymptomatic individuals to the symptomatic individuals; f is the fraction of individual developed by multibacillary leprosy while 1 -f is the fraction of individual developed by paucibacillary leprosy;

x denotes susceptible individuals, y denotes asymptomatic infected individuals, w denotes infected individuals by paucibacillary leprosy; and z denotes infected individual by multibacillary leprosy.

The corresponding fractional model with Caputo derivatives is given by

               C D η t x(t) = p - (β m z + β ρ w) x x + y + z + w -µx, C D η t y(t) = (β m z + β ρ w) x x + y + z + w -θy -µy, C D η t z(t) = f θy -µz, C D η t w(t) = θ(1 -f )y -µw, (3)
where C D η t denotes the Caputo-type fractional derivative of order η. To system (3), we add the following initial conditions:

x(0) = x 0 > 0, y(0) = y 0 ≥ 0, z(0) = z 0 ≥ 0, and w(0) = w 0 ≥ 0.
Without loss of generality, the above model (2) (resp. ( 3)) is defined in the following absorbed

and bounded set Π = (x(t), y(t), z(t), w(t)) ∈ R 4 + : x(t) + y(t) + z(t) + w(t) ≤ p µ [8].

Existence of steady states

Let us defined the following threshold called the basic reproduction number

R 0 = θ (f β m + (1 -f )β ρ ) (θ + µ)µ . (4)
The following result holds.

Theorem 1: Leprosy model (2) (resp. ( 3)) admits two staedy states: the Leprosy-free equilibrium E 0 = p µ , 0, 0, 0 , and an unique Leprosy-endemic equilibrium

E 1 = p (µ (R 0 -1) + µ) 1, µ (R 0 -1) (θ + µ) , f θµ (R 0 -1) µ(θ + µ) , (1 -f )θµ (R 0 -1) µ(θ + µ) which exists if and only if R 0 > 1.
Proof. Equating the right-hand sides of (2) (resp. ( 3)) by zero, and noting that

x * + y * + z * + w * = p µ
, it follows that model (2) (resp. ( 3)) has two equilibrium points: the diseasefree equilibrium E 0 = p µ , 0, 0, 0 , and the endemic equilibrium E 1 = (x * , y * , z * , w * ) where

x * = p λ + µ , y * = λx * (θ + µ) , z * = f θy * µ , w * = θ(1 -f )y * µ , with λ = µ (R 0 -1). Note that E 1 exists if and only if R 0 > 1.
This ends the proof.

Stability analysis of the Leprosy-free equilibrium

The Jacobian matrix of system (2) (resp. ( 3)) evaluated at the Leprosy-free equilibrium

E 0 = p µ , 0, 0, 0 , is given by J (E 0 ) =     -µ 0 -β m -β ρ 0 -(θ + µ) β m β ρ 0 f θ -µ 0 0 θ(1 -f ) 0 -µ     .
The characteristic polynomial of J (E 0 ) is given by P(X)

:= -(X+µ) (a 3 X 3 + a 2 X 2 + a 1 X + a 0 ) , where a 3 = 1, a 2 = 2µ + (θ + µ), a 1 = µ [µ + (θ + µ)(2 -R 0 )], and
a 0 = µ 2 (θ + µ)(1 -R 0 ).
The roots of P(X) are X 1 = -µ and those of the polynomial P 1 (X) := (a 3 X 3 + a 2 X 2 + a 1 X + a 0 ). Note that a 0 > 0 ⇐⇒ R 0 < 1. Also, R 0 < 1 ensures that a 3 , a 2 , a 1 > 0.

For the model (2), the characteristic equation [START_REF] Abboubakar | Fractional dynamics of typhoid fever transmission models with mass vaccination perspectives[END_REF] is given by det

[s (I 4 -(1 -η)J (E 0 )) -ηJ (E 0 )] = 0, which is equivalent to [s(1 + µη 1 ) + µη] 2 (A 2 s 2 + A 1 s + A 0 ) = 0, where A 2 = k 1 (1 -R 0 ) (η -1) 2 µ + (1 -η)µ + k 1 (1 -η) + 1 , A 0 = k 1 η 2 µ (1 -R 0 ), and A 1 = [2k 1 η (1 -R 0 ) (1 -η) µ + η (µ + k 1 )], with η 1 = 1 -η, k 1 = θ + µ.
Solutions of the above equation are s = -µη 1 + µη 1 < 0 and those of (A 2 s 2 + A 1 s + A 0 ). The conditions R 0 < 1 ensures that coefficients A 2 , A 1 , and A 0 are positive, and thus the solutions of (A 2 s 2 + A 1 s + A 0 ) = 0 are always negative. We thus resume the above analysis as follows:

Theorem 2:

For the model (2) (resp. (3)), the Leprosy-free equilibrium E 0 = p µ , 0, 0, 0 is locally asymptotically stable in Π whenever R 0 < 1.

We also claim the following result.

Theorem 3:

For the model (2) (resp. ( 3)), the Leprosy-free equilibrium E 0 = p µ , 0, 0, 0 is globally (resp.

uniformly) asymptotically stable in Π whenever R 0 < 1.

Proof. Let us consider the following Lyapunov function:

M(y(t), z(t), w(t)) := y(t) + β m µ z(t) + β ρ µ w(t), (5)
The derivative of M is given by

Ṁ (y(t), z(t), w(t)) = a 1 ẏ(t) + a 2 ż(t) + a 3 ẇ(t) = a 1 (β m z + β ρ w) x x + y + z + w -(θ + µ)y + a 2 (f θy -µz) + a 3 (θ(1 -f )y -µw) ≤ (a 2 f θ -a 1 (θ + µ) + a 3 θ(1 -f )) y + (a 1 β m -a 2 µ) z + (a 1 β ρ -a 3 µ) w = a 1 (θ + µ) β m µ(θ + µ) f θ + β ρ µ(θ + µ) θ(1 -f ) -1 y = a 1 (θ + µ) (R 0 -1) y. (6)
It then follows that R 0 < 1 ⇐⇒ Ṁ < 0, and Ṁ = 0 if and only if

R 0 = 1 or y = 0. Replacing y = 0 in (2) (resp. ( 3
)) gives x = x = p µ and z = w = 0. So that, lim t-→∞ (x(t), y(t), z(t), w(t)) -→ p µ
, 0, 0, 0 := E 0 . Thus (by [START_REF] Wojtak | Uniform asymptotic stability of a fractional tuberculosis model[END_REF]), we conclude that the Leprosy-free equilibrium point E 0 of model (2) (resp. ( 3)) is globally (resp. uniformly) asymptotically stable in Π whenever R 0 < 1.

Stability analysis of the endemic equilibrium

The jacobian matrix of system (2) (resp. ( 3)) evaluated at the endemic equilibrium point E 1 = (x * , y * , z * , w * ) is given by

J (E 1 ) =         -µ - (y * + z * + w * )λ * N * - λ * x * N * -βmx * (x * + y * + w * ) + βρx * w * (N * ) 2 -βρx * (x * + y * + z * ) + βmx * z * (N * ) 2 λ * (y * + z * + w * ) N * -k 1 - λ * x * N * βmx * (x * + y * + w * ) -βρx * w * (N * ) 2 βρx * (x * + y * + z * ) -βmx * z * (N * ) 2 0 f θ -µ 0 0 (1 -f )θ 0 -µ        
where

N * = x * + y * + z * + w * = p µ . The characteristic equation of J (E 1 ) is given by -(X + µ) 2 (c 2 X 2 + c 1 X + c 0 ) = 0, where c 2 = R 2 0 k 1 (b ρ (1 -f ) + f b m ) > 0, c 1 = (1 -f )((R 0 -1) 2 R 0 µ 2 + (2R 0 -1)R 0 k 1 µ + R 2 0 k 2 1 )β ρ + (R 0 -1) 2 R 0 (f β m + R 0 k 1 )µ 2 + R 0 (2R 0 -1)k 1 f β m µ + R 2 0 k 2 1 f β m > 0, c 0 = (R 0 -1) µ(2 (R 0 -1) 2 µ 2 + (R 0 -1)R 0 k 1 µ + R 0 k 2 1 )(1 -f )β ρ +2(R 0 -1) 2 (f β m + R 0 k 1 )µ 3 + R 0 k 1 (R 0 -1)(f β m + R 0 k 1 )µ 2 + R 0 k 2
1 f β m µ , Note that c 2 and c 1 are always positive, and c 0 > 0 ⇐⇒ R 0 > 1. Thus, we claim the following result:

Lemma 3:

The unique endemic equilibrium point E 1 of model ( 2) is locally asymptotically stable in Π whenever R 0 > 1.

We also claim what follows.

Theorem 4:

If R 0 > 1, then the unique endemic equilibrium point E 1 of model (2) (resp. ( 3)) is globally asymptotically stable in Π provided that

1 - λ λ * 1 - x x * y * y ≥ 0. (7)
Proof. To prove the global (uniformly) asymptotic stability of the unique endemic equilibrium point E 1 = (x * , y * , z * , w * ) of model ( 2) (resp. ( 3)) when R 0 > 1, we define the following Lyapunov function ( [START_REF] Nkague Nkamba | Global stability of a sveir epidemic model: application to poliomyelitis transmission dynamics[END_REF])

N = (µz * + µw * ) λ * x * x -x * -x * ln x x * + (µz * + µw * ) λ * x * y -y * -y * ln y y * + z -z * -z * ln z z * + w -w * -w * ln w w * (8)
The time derivative of N is given by

Ṅ = (µz * + µw * ) λ * x * 1 - x * x x * + (µz * + µw * ) λ * x * 1 - y * y y * + 1 - z * z z * + 1 - w * w w * = b 1 1 - x * x (p -λx -µx) + b 2 1 - y * y (λx -θy -µy) + 1 - z * z (f θy -µz) + 1 - w * w (θ(1 -f )y -µw) (9)
At the equilibrium we have the following relations p = λ * x * + µx * , λ * x * = (µ + θ)y * , f θy * = µz * , and θ(1 -f )y * = µw * . Using the these relations in Eq. ( 9), and after few algebraic computations, we obtain

Ṅ = 1 λ * x * (µz * + µw * ) µx * 2 - x x * - x * x + µz * 4 - x x * y * y - z z * - z * z y y * - x * x + µw * 4 - x x * y * y - w w * - w * w y y * - x * x -µz * 1 - λ λ * 1 - x x * y * y -µw * 1 - λ λ * 1 - x x * y * y . ( 10
)
The fist three terms of (10) are negative since the arithmetic mean exceeds the geometric mean. Together with condition [START_REF] Mo Haroun | Clinical characteristics of neuropathic pain in leprosy and associated somatosensory profiles: a deep phenotyping study in india[END_REF], it follows that the remaining last two terms of (10) are also negative. Thus, Ṅ < 0. So lim t-→∞ (x(t), y(t), z(t), w(t)) -→ (x * , y * , z * , w * ). By the LaSalle invariance principle [START_REF] Joseph | The stability of dynamical systems[END_REF], it follows that the unique endemic equilibrium point E 1 of Leprosy model ( 2) is globally asymptotically stable (GAS) in Π whenever R 0 > 1.

From [START_REF] Boukhouima | Lyapunov functions for fractional-order systems in biology: Methods and applications[END_REF], we note that the Lyapunov function N for ( 2) is also a Lyapunov function for the Leprosy fractional model [START_REF] Mushayabasa | Understanding noncompliance with who multidrug therapy among leprosy patients: insights from a mathematical model[END_REF]. Thus The unique endemic equilibrium of the fractional model ( 3) is globally asymptotically stable whenever R 0 > 1.

Existence and uniqueness of solutions of the fractional model

The objective of this part is to show, by using the theory of the Banach fixed point, the existence and the uniqueness of the solutions of the fractional model ( 3) with the initial conditions. To this aim, we denote by Q the Banach space for continuous functions with real values over an interval K with the associated norms (x, y, z, w) = x + y + z + w , where

x = sup {| x(t) |: t ∈ K}, y = sup {| y(t) |: t ∈ K}, z = sup {| z(t) |: t ∈ K}, w = sup {| w(t) |: t ∈ K}, and Q = ε(K) × ε(K) × ε(K) × ε(K)
, with ε(K) the Banach space for continuous functions with real values on K and the above associated norms. The fractional system (3) can be written in the form :

D η t x(t) = G 1 (t, x), D η t y(t) = G 2 (t, y), D η t z(t) = G 3 (t, z), D η t w(t) = G 1 (t, w), (11) with
G 1 (t, x) = p (β m z + β ρ w) x x + y + z + w -µx, G 2 (t, y) = (β m z + β ρ w) x x + y + z + w -θy -µy, G 3 (t, z) = f θy -µz, G 4 (t, w) = θ(1 -f )y -µw. (12)
By applying the fractional integral operator in equation ( 11), we obtain:

x(t) -x(0) = 1 Γ(η) t 0 (t -χ) η-1 G 1 (χ, x)dχ, y(t) -y(0) = 1 Γ(η) t 0 (t -χ) η-1 G 2 (χ, y)dχ, z(t) -z(0) = 1 Γ(η) t 0 (t -χ) η-1 G 3 (χ, z)dχ, w(t) -w(0) = 1 Γ(η) t 0 (t -χ) η-1 G 4 (χ, w)dχ (13)
The kernels G i , i = 1, 2, 3, 4, satisfy the Lipschitz and contraction conditions if the following inequality holds:

0 ≤ V i < 1, i = 1, 2, 3, 4, (14)
where

V 1 = (β m κ 3 + β ρ κ 4 + µ) , V 2 = κ 1 (β m κ 3 + β ρ κ 4 + µ) , V 3 = V 4 = µ, x = κ 1 , y = κ 2 , z = κ 3 , w = κ 4 . (15)
We thus claim the following result Theorem 5:

The kernel G 1 satisfies the Lipschitz condition if the following inequality is respected

0 ≤ V 1 = (β m κ 3 + β ρ κ 4 + µ) ≤ 1. (16)
Proof. Consider the kernel G 1 , and x, x 1 any two functions. We have

G 1 (t, x) -G 1 (t, x 1 ) = - (β m z + β ρ w) x x + y + z + w -µx + (β m z + β ρ w) x 1 x 1 + y + z + w + µx 1 ≤ (β m z + β ρ w) (y + z + w) (x + y + z + w)(x 1 + y + z + w) + µ (x -x 1 ) ≤ (β m z +β ρ w +µ) (x -x 1 ) = V 1 (β m κ 3 + β ρ κ 4 + µ) (x -x 1 ) . (17)
Therefore, the Lipschitz condition is fulfilled for G 1 , and if in addition, 0 ≤ V 1 < 1, then it is also a contraction. We get similar results for the other kernels:

G 2 (t, y) -G 2 (t, y 1 ) ≤ V 2 y(t) -y 1 (t) , G 3 (t, z) -G 3 (t, z 1 ) ≤ V 3 z(t) -z 1 (t) , G 4 (t, w) -G 4 (t, w 1 ) ≤ V 4 w(t) -w 1 (t) . ( 18
)
The expressions of the equation ( 13) can be written recursively as:

x n (t) -x(0) = 1 Γ(η) t 0 (t -χ) η-1 G 1 (χ, x n-1 )dχ, y n (t) -y(0) = 1 Γ(η) t 0 (t -χ) η-1 G 2 (χ, y n-1 )dχ, z n (t) -z n (0) = 1 Γ(η) t 0 (t -χ) η-1 G 3 (χ, z n-1 )dχ, w n (t) -w(0) = 1 Γ(η) t 0 (t -χ) η-1 G 4 (χ, w n-1 )dχ (19)
The difference between successive terms for recursive formulas is written:

φ 1n (t) = x n (t) -x n-1 (t) = 1 Γ(η) t 0 (t -χ) η-1 (G 1 (χ, x n-1 ) -G 1 (χ, x n-2 )) dχ, φ 2n (t) = y n (t) -y n-1 (t) = 1 Γ(η) t 0 (t -χ) η-1 (G 2 (χ, y n-1 ) -G 2 (χ, y n-2 )) dχ, φ 3n (t) = z n (t) -z n-1 (t) = 1 Γ(η) t 0 (t -χ) η-1 (G 3 (χ, y n-1 ) -G 3 (χ, y n-2 )) dχ, φ 4n (t) = w n (t) -w n-1 (t) = 1 Γ(η) t 0 (t -χ) η-1 (G 4 (χ, w n-1 ) -G 4 (χ, w n-2 )) dχ, (20)
with initial conditions:x 0 (t) = x(0), y 0 (t) = y(0), z 0 (t) = z(0), w 0 (t) = w(0). Let us take the norm of the first expression of the equation (20)

φ 1n (t) = x n (t) -x n-1 (t) = 1 Γ(η) t 0 (t -χ) η-1 (G 1 (χ, x n-1 ) -G 1 (χ, x n-2 )dχ , ≤ 1 Γ(η) t 0 (t -χ) η-1 (G 1 (χ, x n-1 ) -G 1 (χ, x n-2 )dχ , (21)
Using the Lipschitz condition we have:

x n (t) -x n-1 (t) ≤ 1 Γ(η) V 1 t 0 (t -χ) η-1 x n-1 -x n-2 dχ. (22)
Thus, we obtain

φ 1n (t) ≤ 1 Γ(η) V 1 t 0 (t -χ) η-1 φ 1(n-1) (χ) dχ. (23)
Similar reasoning makes it possible to have:

φ 2n (t) ≤ 1 Γ(η) V 2 t 0 (t -χ) η-1 φ 2(n-1) (χ) dχ, φ 3n (t) ≤ 1 Γ(η) V 3 t 0 (t -χ) η-1 φ 3(n-1) (χ) dχ, φ 4n (t) ≤ 1 Γ(η) V 4 t 0 (t -χ) η-1 φ 4(n-1) (χ) dχ. (24)
Note that The fractional model ( 3) admits a unique solution on t ∈ [0, T ] if the following inequality is satisfied

x n (t) = n i=1 φ 1i (t), y n (t) = n i=1 φ 2i (t), z n (t) = n i=1 φ 3i (t), w n (t) =
1 Γ(η) V i b η ≤ 1, i = 1, 2, ..., 4. (26)
Proof. The proof follows the proof of Theorem 4 in [START_REF] Abboubakar | Projections and fractional dynamics of the typhoid fever: A case study of mbandjock in the centre region of cameroon[END_REF].

IV NUMERICAL SCHEME AND RESULTS

Numerical scheme

In what follows, we will use the Adams-Bashforth-Moulton method (see [START_REF] Abboubakar | Projections and fractional dynamics of the typhoid fever: A case study of mbandjock in the centre region of cameroon[END_REF][START_REF] Diethelm | An algorithm for the numerical solution of differential equations of fractional order[END_REF]) to construct a numerical scheme for the fractional model (3). To this aim, let us consider the uniform discretization of [0, a] given by t m = mℵ, m ∈ [0; N ] ∩ N where ℵ = a/m denotes the step size. For a given approximation Z ℵ (t i ) ≈ Z(t i ), the next approximation Z ℵ (t i+1 ) is obtain (using the predictor-corrector method) as follows:

Predictor: Z p ℵ (t m+1 ) = ϕ -1 l=0 t l n+1 l! Z l 0 + 1 Γ(η) m l=0 b l,m+1 G (t l , Z ℵ (t l )) ; Corrector: Z ℵ (t m+1 ) = ϕ -1 l=0 t l n+1 l! Z l 0 + h η Γ(2 + η) G t l+1 , Z ℵ ℵ (t l+1 ) + ℵ η Γ(2 + η) m l=0 c l,m+1 G (t l , Z ℵ (t l )) ; with c l,m+1 =    m 1+ϕ -(m -ϕ)(m + 1) ϕ , if l = 0, (m -l + 2) 1+ϕ + (m -l) 1+ϕ -2(m -l + 1) 1+ϕ , if 1 ≤ l ≤ m, 1 if l = m + 1, and b l,m+1 = ℵ ϕ ϕ [(m -l + 1) ϕ -(m -l) ϕ ].

Numerical results

For numerical simulations, we consider the following set of parameter values: The theoretical results of the fractional-order model are verified by varying the fractional-order parameter η. Indeed, we demonstrate our obtained analytical results numerically in Section III.

In Figure 1, we see that when R 0 < 1, the solutions converge to the Leprosy-free equilibrium, while in Figure 2, the solutions converge to the endemic equilibrium point whenever R 0 > 1.

In Figure 2, we also see that the population of each class or compartment decreases when the fractional-order decreases.

V CONCLUSION

In this work , we extended the works of Raza & Rafiq [START_REF] Raza | Modeling and transmission dynamics of leprosy disease: Via numerical methods[END_REF], which consists of a system of Ordinary Differential Equations, by replacing integer derivatives with fractional derivative in the Caputo sense, and mass action incidence by standard incidence. We computed the new basic reproduction number R 0 and proved the existence of two steady states named the Leprosy-free equilibrium which always exists, and the unique endemic equilibrium point which exists if and only if R 0 > 1. We also proved the global stability of both equilibrium points for both models. Indeed, by constructing two lyapunov functions, we proved that the leprosy diseasefree equilibrium (resp. the unique endemic equilibrium point) is globally asymptotically stable whenever the basic reproduction number is less that unity (R 0 < 1) (resp. greater than unity (R 0 > 1)). Then, we studied the existence and the uniqueness of the solutions of the fractional model using fixed point theory. Using the Adams-Bashforth-Moulton method to construct the numerical scheme, we performed numerical simulations to validate our analytical results, as well as to see the impact of varying the fractional parameter on the disease spread. Indeed, when R 0 < 1, the solutions converge to the Leprosy-free equilibrium while the solutions converge to the endemic equilibrium point whenever R 0 > 1. Also, the population of each class or compartment decreases with the decrease of the fractional-order.

φ

  4i (t). (25) Now let's show the uniqueness of the model solution. We claim the following Theorem 6:

1 .

 1 p = 100; m = 1/55.5; β m = β ρ = 0.019; θ = 0.19 and f = 0.7 which give R 0 = 0.9632 < 1; 2. p = 100; m = 1/55.5; β m = β ρ = 0.03; θ = 0.19 and f = 0.7 which give R 0 = 1.5208 > 1;

Figure 1 :

 1 Figure 1: Time-series of state variables for R 0 = 0.9632 < 1 and different values of the fractional-order η ∈ {1; 0.9; 0.7; 0.6}.

Figure 2 :

 2 Figure 2: Time-series of state variables for R 0 = 1.5208 > 1 and different values of the fractional-order η ∈ {1; 0.9; 0.7; 0.6}.

A ACKNOWLEDGEMENTS

The first author thanks the Zukunftskolleg of the University of Konstanz for their hospitality during his research stay which permits him to improve this work. The authors express their gratitude to the anonymous reviewers for their comments and suggestions which helped to improve the manuscript.


Salem Benferhat

Mouslim Tolba

Karim Tabia

Abdelkader Belkhir

Handling Capabilities in Security Policies

Keywords:

come

INTRODUCTION

Access Control plays a crucial role in securing information or physical systems. For instance, to secure different areas of an airport, it is important to represent access control security policies that provide the list of authorisations /privileges associated with each user (passengers, grounded hostess, etc) of the airport.

In the literature, a large number of access control models have been proposed. The Lampson model [START_REF] David F Ferraiolo | Proposed nist standard for role-based access control[END_REF] introduced matrix access control where a user gets a permission to run some action on an object, only if such action is stated in the matrix access. HRU [START_REF] Michael A Harrison | Protection in operating systems[END_REF] also uses an access matrix and was designed to improve the Lampson model to update security policies using the concept of commands. Discretionary Access Control(DAC) [START_REF] David F Ferraiolo | Proposed nist standard for role-based access control[END_REF] models allow the handling of access rights to each object is in the absolute discretion of the owner or the subject who is responsible. This model is usually implemented with ACL (Access Control Lists). A simple example of DAC model is the one used by UNIX operating system. DAC models are not appropriate for airport security applications. In particular, they do not satisfy the least privilege principle [START_REF] Hu | An empirical study of three access control systems[END_REF].

RBAC (Role Based Access Control) [START_REF] Umar | Attributed role based access control model[END_REF] defines an authorisation model for accessing resources. Its main objective is to compactly describe security policies by introducing the concept of role which is a factorization of assigning permissions in order to prevent more relationships between permissions and users. Authorisation (or permissions) are not directly assigned to user but to their abstraction called role.

Existing access control models consider that actions executed by users are elementary. however, in practice security policies are more defined over sequences of actions rather then over elementary actions.

For instance, in an airport security example, a security policy may concern a simple activity such as checking a luggage of a given passenger. The security policy may also contain authorisation rules that deal with complex activities such as the whole boarding process. This complex activity (boarding process) is in fact a sequence of elementary actions: checking luggage, assigning seats, printing boarding pass,... Another example where both elementary actions and non-elementary actions co-exist is the one of Linux operating system. In Linux systems, the actions (or commands) "ls","grep","type" are high-level actions that are implemented by set of low level actions(system calls).

In [START_REF] Benferhat | Integrating non elementary actions in access control models[END_REF], a slight extension of OrBAC (Organisation based access control) model to integrate non-elementary actions [START_REF] Abou | Policies for Distributed Systems and Networks[END_REF] [5] [START_REF] Kaddani | Towards a model driven security for critical infrastructures using orbac[END_REF]. Non elementary actions are represented by a partial pre order overs pairs (ai,oj) where ai is an elementary action and oj is a concrete object. These non-elementary actions will be simply called plans.

This paper goes one step further by showing how explicit prohibitions can be represented over non elementary actions,which is detailed in next section.

REPRESENTING SEQUENCE OF ACTIONS

In existing access control systems, including the OrBAC model described above, it is assumed that authorisation rules are defined on elementary actions and over concrete objects. This assumption does not hold in general.

In [START_REF] Benferhat | Integrating non elementary actions in access control models[END_REF] a slight extension of OrBAC model called Pl-OrBAC has been proposed. In Pl-OrBAC Both elementary and nonelementary actions can be represented. The main idea is to modify the abstract entity "permission" and the concrete entity "is permitted" in order to deal with non-elementary activities and non-elementary actions respectively. This paper goes one step further and show how to represent and derive concrete prohibitions. Let us first give a brief refresher on OrBAC model.

OrBAC model

Organization-based access control (OrBAC) [7] [6] is an access control model that allows the policy designer to define a security policy in a compact way. OrBAC model is based on the following four principles:

Organization: An organisation may be an institution or an organized group of subjects, playing some role.

Levels of abstraction: A concrete level materialized through the use of three concrete entities: subjects, actions and objects.

Relating abstract authorisation to concrete authorisation: subjects are abstracted into roles. Similarly, an activity is a set of actions to which the same security rule applies. And a view is a set of objects to which the same security rule applies.

Figure 1 shows the interactions between existing entities in the model OrBAC:

Representing explicit prohibitions over sequences of actions

This section shows how to represent and derive explicit prohibitions over non-elementary actions in Pl-OrBAC model. A non-elementary activity, called a generic plan [START_REF] Benferhat | Integrating non elementary actions in access control models[END_REF], is a sequence of elementary activities, to be applied on views, in order to achieve some task. Let GA be a set of activities and GV be a set of views. A generic plan, denoted by the capital letter Pl, is a POS (partially pre-ordered set) Pl=(NE,≺) where NE⊆GAxGV and ≺ is partial pre-order on NE.

The partial pre-order indicates the precedence order between the activities.

In order to take into account the prohibition relations over generic plans, we replace the prohibition and permission relations in OrBAC by new relations called G-prohibition and G-permission. Generic plans (Figure 2) is a new entity that contains generic plans.

At the concrete level, we also need to introduce concrete plans. Concrete plans are directly defined over concrete actions and concrete objects rather then on their abstractions. More precisely let CA be a set of concrete actions, O be a set objects. A concrete plan, denoted by the lower case p, is totally-ordered set p=(E, ≺) where E⊆CA x O and ≺ is a total order on E. In order to take into account the concept of concrete plans, we also need to introduce the new entity, called concrete plan. Concrete permissions and concrete prohibitions, denoted G ispermitted and G isprohibited, is described by Figure 3: In [START_REF] Benferhat | Integrating non elementary actions in access control models[END_REF] an algorithm has been proposed to derive permissions overs concrete plans. Algorithm 1 shows how to derive concrete prohibitions attributed to a particular user u to achieve a particular plan p. Namely, how to derive G isprohibited(org,u,p). The main idea of this algorithm is to see whether there exists a generic G-prohibition rule that applies for the concrete user u and any concrete subplan p' of p. Hence, the idea is to generate all prohibitions GP on generic plans Pl that accept p' as an instantiated plan. An instantiated plan is a concrete plan obtained by replacing roles, activities and views by concrete users, actions and objects respectively. Note that there is an explicit prohibition for a plan p if one can derive an explicit prohibition for each subplan p' of p.

EXAMPLE

Assume that we are interested in modeling access control security rules concerning the boarding process of a given flight. To achieve this task, we need to specify the content of each table and relation of the Pl-OrBAC model.

First, we assume that we only have one organisation, which is "HB", Simply denoted by HB(see Figure 4) Now, we need to specify the list of roles, activities and views used in the information system of the organisation HB:

• Roles: We assume that there are three roles: passengers, ground hostess, ground and security hostess.

• Activities: The activities in HB are: checking luggages, assigning seats and boarding passengers.

• Views: We assume that the list of views is: seats, luggages to check and passengers to board.

The second step is to identify the list of concrete objects in the information system, the list of concrete actions on the information system and the list of concrete users:

• Users: John, Bob, Alice and Pierre.

• Actions: there are five actions: Print luggage tags at air company checking counter, print luggage tags at air company checking kiosks, assign a seat at air company checking counter, assign a seat at air company checking kiosk and use kiosk1 to validate boarding pass.

• Objects: Seat 1 to Seat 400, L1, L2, John, Bob. Figure 7 gives the content of the relation "Use" that relates objects of the information system to views. For instance, the object Seat1 is used as the view Seat, and the concrete object L1 is used as a luggage to check. "context" and its definition relation. In this example, we assume that there are only three contexts, denoted by "flight opened for check in", "flight opened for boarding" and "always". Figures 9 gives the con- The context "always" simply means that no condition is required for achieving some authorisation rules. While the context "Flight open check in" states that authorisation rules only apply if the flight is open for check in. In our example, from the relation "define" the context "flight open for check in". However, the context "flight open for boarding" is false. This means that all authorisation rules that need the context "flight open for boarding" cannot be activated.

The set of authorisations/ prohibitions security rules used by the HB organisation as follows:

• "Grounded hostess" has permission to assign seats without additional condition. Said differently the context of this permission rule is "always".

• "Grounded hostess" has permission to check luggage when a flight is open for check in (namely, in the context flight open for check in)

• It is prohibited for "grounded hostess" to achieve the activity of boarding passengers.

We assume that we have two plans (sequences of elementary activities):

• P1: This generic plan is defined by: (N E1={(checking luggage, luggage), (assigning seats, seats)}, ≺NE 1 ,= ∅)

• P2: This generic plan is defined by: N E1={(checking luggage, luggage), (assigning seats, seats),(boarding passengers, passengers)} with (checking luggage, luggage) ≺NE 2 (boarding passengers, passengers) and (assigning seats, seats) ≺NE 2 (boarding passengers, passengers).

Intuitively, P1 corresponds to the complex activity of check in. while P2 involves the whole boarding process (check in luggages and boarding passengers). ≺NE 1 states that there is no precedence relation between the two elementary activities: check in luggages and assigning seats. ≺NE 2 states that check in luggages (resp assigning seats) should be done before boarding passengers. Given these two generic plans, we have two additional access control security rules:

• Grounded Hostess have permission to achieve P1 in the context of "flight open for check in".

• Security hostess have permission to achieve P2 in the context of flight open for boarding.

• It is prohibited for grounded hostess to achieve P2.

CONCLUSIONS

This paper shows how to represent prohibition rules over non-elementary actions in access control model. We provide a slight extension of OrBAC model and show how to integrate the concepts of generic and concrete plans by means of sequences of actions. A future work is to deal with the problem of handling conflicts when security policies, that use different levels of granularity of actions, co-exists.

Figure 1 :

 1 Figure 1: OrBAC model

Figure 2 :

 2 Figure 2: Representation of generic plans, Gpermission and G-prohibition relations

Figure 3 :

 3 Figure 3: Concrete plans, G-ispermitted and Gisprohibited relations.

Figure 4 :

 4 Figure 4: The content of organisation table.

Figure 5

 5 Figure 5 describes the relation "Empower" that relates users to roles.

Figure 5 :Figure 6

 56 Figure 5: The relation "Empower"Figure6gives the content of the relation "consider" that relates concrete actions used in the information system to general activities:

Figure 6 :

 6 Figure 6: The relation "consider"

Figure 7 :

 7 Figure 7: The relation "use" Figures 8 gives the table"context" and its definition relation. In this example, we assume that there are only three contexts, denoted by "flight opened for check in", "flight opened for boarding" and "always". Figures 9 gives the con-

Figure 8 :

 8 Figure 8: The context table

Figure 9 :

 9 Figure 9: The relation "define"

Figure 10

 10 Figure 10 and 11 give the relations G-permission and Gprohibition :

Acknowledgements

This work has received support from the french national project PEPS SISC INS2I 2016 entitled EPIAGE (Evolution des politiques de contrôle d'accès et gestion d'actions interférentes).


Pauline Souloumiac
email: pauline.souloumiac@cyu.fr

speaker Marthe Lefèvre

Nadaya Cubas

Bertrand Maillot

Yann Klinger

Control of geometrical and mechanical parameters on strike-slip fault segmentation: insights from sandbox experiments

come   L'archive ouverte pluridisciplinaire

Sandbox apparatus and experimental procedure

The specific sandbox for Riedel experiments is composed of two PVC plates simulating the base of the upper crust. One plate is movable and can be pushed forward to simulate a sinistral strike-slip fault at the base of the model thanks to a lead screw. The other plate is fixed. The dimensions of the box (80x210cm) are large enough to ensure that a significant part of the observations escapes boundary effects. The sand pack is flat and the edges are free. Top view photos are taken every 0.5 mm.

We test sand pack varying from 2 to 6 cm thick. To get different internal frictions, the sand is poured in two different mods: (1) sedimented with a sand distributor used to achieve a uniform sand density and a high internal friction (CV32): φint=43.7° and (2) by sprinkling and scraping the sand pack for a lower friction (CV32): φint=35.6°.

A third type of sand with a different grain size range (Ga39) is also tested: φint= 33.4°. Two different basal frictions were tested: φb=13° (sand/PVC) and φb=18° (sand/Alkor foil®). For each experiment, three parameters are measured: the spacing between Riedels (S), the Riedels' length (L) and the angle (α) formed by the Riedel and the direction of the strike slip fault at the base of the model (Fig. 1). In order to obtain satisfactory statistical results and to provide a correlation between parameters, 45 experiments were run for this study.

Experimental results

The thickness of the sand pack has a significant influence on the Riedels spacing. The thicker the sand layer is, the greater the spacing is (and implicitly longer). The thickness and the average spacing between Riedels appear to be linearly correlated (slope ~1.5) (Fig 1).

Figure 2: Normalized length of individual fault segments for several continental strike-slip earthquakes [START_REF] Klinger | Relation between continental strike-slip earthquake segmentation and thickness of the crust[END_REF]Lauer et al., 2018) and for individual analogue-fault segments (Sands 2 and Sand 3). From Lefèvre, 2018 (PhD Thesis).

If the sand layer thickness is constant, the larger the sand internal friction is, the longer the spacing is (Fig. 1).

Similarly, a linear relation relates the thickness and the average spacing between Riedels with the internal friction (slope ~1.5). Obviously, different internal frictions lead to various coefficients for this relation (slope and intercept): a frictional variation of 0.1 corresponds to a slope variation equal to 0.25. Furthermore, it seems that basal friction has no influence on the Riedels. Finally, considering a standard internal friction for the upper crust, this study shows that we are able to retrieve the same length over thickness ratio as for the natural cases (Fig. 2).

Figure 1 :

 1 Figure 1: A -Topview of the sandbox after 11 mm of displacement highlighting the en échelon Riedel faults. [B-E] Comparison between inter-Riedel distance (S) and sand-pack thickness (T) for different frictional and cohesional properties of sand. Modified from Lefèvre et al, 2020.