Didier Dubois
email: dubois@irit.fr

Henri Prade
email: prade@irit.fr

Agnès Rico
email: agnes.rico@univ-lyon1.fr

The logical encoding of Sugeno integrals

Keywords: Discrete Sugeno integrals, Possibilistic logic, Possibility theory

Sugeno integrals are a well-known family of qualitative multiple criteria aggregation operators. The paper investigates how the behavior of these operators can be described in a prioritized propositional logic language, namely possibilistic logic. The case of binary-valued criteria, which amounts to providing a logical description of the fuzzy measure underlying the integral, is first considered. The general case of a Sugeno integral when critersia are valued on a discrete scale is then studied.

Introduction

Simple multiple criteria aggregation attitudes are rather easy to grasp. Thus, a strict conjunctive attitude based on the minimum operator amounts to saying that the global evaluation reflects the worst rating among local evaluations according to each criterion. With an averaging attitude between two criteria, a global medium score corresponds to having either both criteria half satisfied or one poorly satisfied and the other one fully satisfied. When more sophisticated aggregation operators are used, it becomes difficult to figure out what is their exact meaning from a preference representation point of view, and more generally to provide explanations on the reasons why an object receives some global score [START_REF] Labreuche | A general framework for explaining the results of a multi-attribute preference model[END_REF].

In this paper, we consider an important family of qualitative aggregation operators, namely Sugeno integrals [START_REF] Sugeno | Theory of fuzzy integrals and its applications[END_REF][START_REF] Sugeno | Fuzzy measures and fuzzy integrals: a survey[END_REF]. They range between minimum and maximum operators, and behave more generally as the median of the normalized ratings according to the various criteria, together with importance levels of groups of best satisfied criteria. In Sugeno integrals, each subset of criteria is indeed associated with an importance level, which enables some synergy between them to be modeled. Sugeno integrals have found many applications in multi-criteria decision aid [START_REF] Grabisch | A decade of application of the Choquet and Sugeno integrals in multi-criteria decision aid[END_REF]. In the following we investigate the possibility of providing an equivalent logical representation of Sugeno integrals in the setting of possibilistic logic where classical logic propositions are associated with priorities.

The contribution of the paper is first to provide a set of results for converting Sugeno integrals into two kinds of possibilistic logic formats. Another contribution is to show that our encoding comes close to a previous proposal by Greco et al. [START_REF] Greco | Axiomatic characterization of a general utility function and its particular cases in terms of conjoint measurement and rough-set decision rules[END_REF] using the so-called single-graded rules. These results may shed some light on the intended meaning of the aggregation, in logical terms, for instance when Sugeno integrals are obtained by means of a learning procedure [START_REF] Prade | Elicitating Sugeno integrals: methodology and a case study[END_REF][START_REF] Prade | Elicitation of Sugeno integrals: a version space learning perspective[END_REF] from observed data describing how people associate a global evaluation to elementary ones. Indeed, we may then provide some explanations on the evaluation procedure used by the persons supplying the data, showing them which rules they implicitly followed.

The paper 1 is structured as follows. The next section provides notations and background regarding discrete Sugeno integrals on the one hand, and possibilistic logic on the other hand. Section 3 then discusses the logical representation of a fuzzy measure, which corresponds to a global evaluation based on binary valued criteria. Section 4 deals with the general case of a Sugeno integral when criteria are graded on a discrete bounded scale. Section 5 discusses related works and especially the one by Greco et al. [START_REF] Greco | Axiomatic characterization of a general utility function and its particular cases in terms of conjoint measurement and rough-set decision rules[END_REF], before concluding.

Notations and background

We consider a set P = {1, . . . , n} of criteria (properties) and a set X of alternatives evaluated according to each criterion. We suppose that all criteria share the same evaluation scale, a finite totally ordered set L with k + 1 levels denoted by 0

= 1 < • • • < k+1 = 1. Each alternative x ∈ X is encoded as a vector of ratings x = (x 1 , . . . , x n ) ∈ L n
where x i is the rating of x with respect to criterion i.

The aim of this paper is to bridge the gap between two objects of different nature, introduced in different information modeling perspectives, namely discrete Sugeno integrals and possibilistic knowledge bases. We now recall the necessary background on both of them successively.

Discrete Sugeno integral

The discrete Sugeno integral is used in qualitative decision theory and multiple criteria decision-making in order to synthesize the partial ratings of an object into a global evaluation. Its definition is based on fuzzy measures [START_REF] Sugeno | Theory of fuzzy integrals and its applications[END_REF], also called capacities after Choquet [START_REF] Choquet | Theory of capacities[END_REF]. Definition 1. A fuzzy measure, or capacity, : 2 P → L is an increasing set function (in the wide sense: (T ) ≤ (S) if T ⊆ S ⊆ P) such that (∅) = 0 and (P) = 1.

The fuzzy measure defines an importance system on groups of criteria. In the following, for criteria i, j, k, importance levels ({i}) and ({ j, k}) are respectively denoted by i and j,k for short. Clearly, i,i = i , j,k = k, j and more generally, i, j,. ..,r = (i), ( j),. .., (r ) for any permutation of the indices. The increasingness of the fuzzy measure ensures that ∀i, j, . . . , r, i ≤ i, j ≤ i, j,. ..,r .

Capacities can represent synergies among criteria. For instance, the case when max( i , j ) < i, j expresses that criteria i and j are not redundant, and together they have a higher importance than any individual one, which can be viewed as a form of positive synergy between them. More generally, if (T ) > max S⊂T (S), it means that the group T of criteria brings about some strength none of its subsets possesses. A capacity such that (T ) = max S⊂T (S) expresses the case where some criteria in T are redundant, even if of various individual degrees of importance. When (T ) = max i∈T i (this is the maxitivity property), criteria are individually redundant and represents a possibility measure [START_REF] Dubois | Possibility theory: qualitative and quantitative aspects[END_REF], as discussed in the next subsection. In that case, knowing the importance degrees of single criteria is enough to reconstruct , and i = 1 for at least one i. The mapping assigning degree i to each i = 1, . . . , n is then called a possibility distribution, often denoted by .

Remark.

In numerical approaches to criteria aggregation using Choquet integrals (see, e.g., [START_REF] Grabisch | A decade of application of the Choquet and Sugeno integrals in multi-criteria decision aid[END_REF]), weights of elementary criteria can be added, and the positive synergy between two criteria i, j is modeled by a super-additive weight i, j > i + j . Independent criteria are such that i, j = i + j . A qualitative approach cannot express this kind of independence. However, in the qualitative approach (T ) represents a kind of importance level of the group T of criteria, but it acts as a threshold, not as a weight. In this context, where importance levels can only be compared, the inequality max( i , j ) < i, j can thus be interpreted as a form of positive synergy, understood as non-redundancy, while in the numerical setting with weights, the case when max( i , j ) < i, j < i + j corresponds to a negative synergy.

Given a fuzzy measure, we can compute its qualitative Möbius transform which contains the minimal amount of information sufficient to reconstruct the fuzzy measure. Definition 2. The qualitative Möbius transform [START_REF] Mesiar | k-order Pan-discrete fuzzy measures[END_REF][START_REF] Grabisch | The Möbius transform on symmetric ordered structures and its application to capacities on finite sets[END_REF] of the fuzzy measure is a set-function # on P defined by

∀T ⊆ P, # (T ) = (T ), if (T ) > max S⊂T (S)

0, otherwise

It can be checked that

∀T ⊆ P, (T ) = max S⊆T # (S).
In analogy with the theory of belief functions [START_REF] Shafer | A Mathematical Theory of Evidence[END_REF], the sets T such that # (T ) 0 are called the focal sets of and form the set F . Note that contrary to a usual mass function in belief function theory, the values # (T ) are strictly increasing under inclusion on F . Moreover, # (T ) = 1 for at least one focal set T. # can thus be viewed as a possibility distribution on the set of subsets of criteria. It coincides with a possibility distribution over singletons if and only if the fuzzy measure is maxitive. The set of focal sets represents all groups of criteria that are not redundant as a whole. The Sugeno integral of an alternative x with respect to the fuzzy measure is often defined as follows [START_REF] Sugeno | Theory of fuzzy integrals and its applications[END_REF]:

Definition 3. (x) = k+1 max i=1 min( i , (X i ))
where

∀ ∈ L , X = {i ∈ P|x i ≥ }.
When x is a Boolean alternative (x i ∈ {0, 1}), (x) = (T x ) where T x = {i, x i = 1} is the set of criteria satisfied by x. This equality provides a simple interpretation of the values of the fuzzy measure as the global evaluation of objects fully satisfying some criteria and fully violating other ones. The above expression makes it clear that (x) is the median value in the set L ∪ { (X i ), i = 2, . . . , k + 1} [START_REF] Kandel | Fuzzy sets, fuzzy algebra, and fuzzy statistics[END_REF].

The Sugeno integral can be equivalently written under various forms [START_REF] Sugeno | Theory of fuzzy integrals and its applications[END_REF][START_REF] Sugeno | Fuzzy measures and fuzzy integrals: a survey[END_REF][START_REF] Dubois | Qualitative possibility functions and integrals[END_REF][START_REF] Marichal | Aggregation Operations for Multicriteria Decision Aid[END_REF][START_REF] Marichal | On Sugeno integral as an aggregation function[END_REF]:

Proposition 1. (x) = max T ⊆P min (T ), min i∈T x i = min T ⊆P max (P\T ), max i∈T x i = k+1 max i=1 min( i , (X i )) = k+1 min i=1 max( i , (X i+1 )) (wher e X k+2 = ∅).
Note that the knowledge of the qualitative Möbius transform is enough to calculate the Sugeno integral in the form

(x) = max T ⊆F min # (T ), min i∈T x i
Remark. We cannot write (x) = # (x) without ambiguity as the equality max k+1 i=1 min( i , (X i )) = max k+1 i=1 min( i , # (X i )) generally does not hold.

When the evaluation scale is the unit interval [0, 1], it has been noticed [START_REF] Marichal | Aggregation Operations for Multicriteria Decision Aid[END_REF][START_REF] Dubois | The use of the discrete Sugeno integral in decision-making: a survey[END_REF] that Sugeno integral coincides with idempotent lattice polynomials, that is, functions P(x 1 , . . . , x n ) defined by combining variables x 1 , . . . , x n (representing the degrees of fulfillment of n properties), and constants c 1 , . . . , c m in [0, 1], with min, max, and parentheses, and such that the limit conditions P(1, . . . , 1) = 1 and P(0, . . . , 0) = 0 hold (see also [START_REF] Couceiro | Characterizations of discrete Sugeno integrals as polynomial functions over distributive lattices[END_REF] in the more general case of distributive lattices). Thus, Boolean combinations of properties, involving no negation, are particular cases of Sugeno integrals. This suggests that Sugeno integrals may be viewed not only as an evaluation tool, but as a knowledge representation tool as well.

We now present a reminder on two dual representation possibilistic logic formats that we want to relate to Sugeno integrals.

Possibilistic logic: conjunctive and disjunctive normal forms

Consider a propositional language L containing formulas denoted by , , etc. The logical negations, conjunctions and disjunctions are respectively denoted by ¬, ∧ and ∨. Let be the set of interpretations of L. Let M( ) be the set of models of , the interpretations where is true.

N-bases

A possibilistic logic base B N is a set of pairs {( j , j ) | j = 1, . . . , m} where j ∈ L is a propositional logic formula and j ∈ L is a priority level [START_REF] Dubois | Possibilistic logic: a retrospective and prospective view[END_REF]. We assume that L is equipped with its order-reversing map that we denote by 1 -• : 1i = n-i+1 . Each formula ( j , j ) means that N ( j ) ≥ j where N is a necessity measure, 2 i.e., a capacity satisfying the property N ( ∧ ) = min(N ( ), N ( )). A necessity measure is associated to a possibility distribution , a mapping → L, as follows:

N ( ) = min / ∈M( ) (1 -( )). The capacity ( ) = 1 -N (¬ ) = max ∈M( ) ( ) is the possibility measure associated to N.
At the semantic level, to the base B N is associated the least informative possibility distribution on the set of interpretations induced by the constraints N ( j ) ≥ j for j = 1, . . . , m:

N B ( ) = m min j=1 ( j , j ) ( ) where ( j , j ) ( ) = 1, if ∈ M( j ) 1 -j , if / ∈ M( j ).
An interpretation is all the more possible as it does not violate any formula j having a higher priority level j . Hence, this possibility distribution is expressed as a min-max combination of the form:

N B ( ) = m min j=1 max(1 -j , I M( j ) ( ))
where I M( j ) is the characteristic function of M( j ).

If the necessity measure N is based on the possibility distribution , it holds that N ( j ) ≥ j , ∀ j = 1, . . . , m if and only if ≤ N B . So, the possibilistic base B N is a description of a possibility distribution "from above". A possibilistic base B N can be always rewritten as a base where the formulas i are clauses (without altering the distribution N B ), thanks to the decomposability of necessity measures with respect to conjunction. Indeed, any formula ∈ L can be written as a conjunction ≡ ∧ j=1 j where j is a clause. And ( , ) corresponds to the same possibility distribution as {( j , ) : j = 1, . . . }. Thus, we can still see B N as a conjunction of weighted clauses, i.e., we get an extension of the conjunctive normal form of propositional bases to possibilistic logic. Moreover, there is another possible understanding of the degree of satisfaction N B ( ). Consider B N as a fuzzy set of classical formulas, and denote by N , the associated necessity measure on B N , defined by ∀A ⊆ { 1 , . . . , n }, N (A) = min j / ∈A (1j ). For all j = 1, . . . , n we have j = 1 -N ({ j } c ). Note that we do not assume that there exists i ∈ {1, . . . , m} such that i = 1. So the necessity measure defined above is possibly sub-normalized. More precisely, we have

N (∅) = min m i=1 (1 -i ) instead of N (∅) = 0. Let B N = { : ( , ) ∈ B N
, } be the set of logical formulas for which is a model. We have

B ( ) = m min j=1 max(1 -j , I M( j ) ( )) = min j / ∈B (1 -j ) = N (B N ).
2 N ( j ) is short for N (M( j )), i.e. it assigns the same value to semantically equivalent propositions.

-bases

A dual representation in possibilistic logic is based on guaranteed possibility measures [START_REF] Dubois | Possibility theory as a basis for preference propagation in automated reasoning[END_REF][START_REF] Dubois | Possibility theory: qualitative and quantitative aspects[END_REF]. We consider another type of logical formula (now denoted between brackets rather than parentheses) as a pair [ , ], expressing the constraint ( ) ≥ , where is a guaranteed possibility measure characterized by

( ∨ ) = min( (), ( ))
and (∅) = 1. Note that is decreasing with respect to logical entailment since () = min ( ) (hence one may speak of 'anti-measure' by contrast with the possibility and necessity measures and N). In such a context, a base

B = {[ i , i ] | i = 1, . . . , n} is associated to the distribution B ( ) = max i=1,. ..,n [ i , i ] ( ) with [ i , i ] ( ) = i , if ∈ M( i ) 0, otherwise
So, if the anti-measure is based on the possibility distribution , it holds that ( i ) ≥ i , ∀i = 1, . . . , n if and only if ≥ B . So, the possibilistic base B is a description of a possibility distribution "from below". A dual possibilistic base B can always be rewritten as a base in which the formulas j are conjunctions of literals (cubes) without altering B , thanks to the decomposability of guaranteed possibility measures with respect to disjunction. So B can be seen as a weighted combination of cubes, i.e, as an extension of the disjunctive normal form.

A possibilistic logic base B (a -base for short) expressed in terms of a guaranteed possibility measure can always be rewritten equivalently in terms of a standard possibilistic logic base B N (an N-base for short) using necessity measures [START_REF] Benferhat | Logical representation and fusion of prioritized information based on guaranteed possibility measures: application to the distance-based merging of classical bases[END_REF] and conversely, enforcing the equality N B = B . The transformation from N B to B corresponds to writing the min-max expression of N B as a max-min expression by applying the distributivity of min over max.

Proposition 2. The N-base B N = {( j , j ) | j = 1, . . . , m} is semantically equivalent to the -base B = {[∧ j∈J j , min k / ∈J (1 -k )] : J ⊆ {1, . . . , m}}.
Proof. Any expression of the form min m j=1 max(a j , b j ) can be rewritten as max J ⊆{1,. ..,m} min(min j∈J a j , min j / ∈J b j ), where min j∈∅ a j = 1. Hence

N B ( ) = m min j=1 max(1 -j , I M( j ) ( )) = max J ⊆{1,. ..,m} min min k / ∈J (1 -k ), I M(∧ j∈J j ) ( )
where I M(∧ j∈J j ) ( ) = min j∈J I M( j ) ( ). ç

Note that it looks as if the translated knowledge base is exponentially larger than the original one. However it can be simplified. Indeed, suppose, without loss of generality that 1

> 2 > • • • > m (recall that if j = k it is possible to replace {( j , j ), ( k , k )} by {( i ∧ k , k )}
) and m+1 = 0 by convention. Then it is easy to check that max J ⊆{1,. ..,m} min min

k / ∈J (1 -k ), I M(∧ j∈J j ) ( ) = max k=1,. ..,m+1 min 1 -k , I M(∧ k-1 j=1 j ) ( )
which corresponds to the -base

B = {[∧ k-1 j=1 j , 1 -k ] : k = 1, . . . , m + 1}, with ∧ 0 j=1 j = ⊤ (tautology). Of course, likewise the -base B = {[ i , i ] | i = 1, . . . , n} is semantically equivalent to the N-base B N = ∨ i∈J i , max k / ∈J (1 -k ) : J ⊆ {1, . . . , m} ,
which can be simplified as

B N = {(∨ k-1 i=1 i , 1 -k ) : k = 1, . . . , n + 1}, with 1 > 2 > • • • > m > n+1 = 0, ∨ 0 j=1 j = ⊥ (contradiction), by convention. Example 1. B = {[ 1 , 1], [ 2 , ]} with < 1. Let E i = M( i ). We have ( ) = max(I E 1 ( ), min(I E 2 ( ), )) = min(max(I E 1 ( ), I E 2 ( ), 0), max(I E 1 ( ), )). It does correspond to B N = {( 1 ∨ 2 , 1), ( 1 , 1 -)}.
Note that this procedure generalizes the mutual transformation of a disjunctive normal form into a conjunctive normal form to the gradual case. The existence of equivalent min-max and max-min expressions for the semantics of possibilistic logic bases echoes similar observations that can be made on the equivalent expressions of Sugeno integrals given in Proposition 1.

Fuzzy measures and possibilistic logic bases

This section presents a method for encoding a fuzzy measure by means of a possibilistic logic base with positive clauses (i.e., clauses with positive literals), and conversely shows that a general possibilistic logic base induces a general set function. Generally, the obtained set function is non-monotonic, but necessary and sufficient conditions are presented for a possibilistic logic base to encode a fuzzy measure. In the decision evaluation context, it means that, in this section, we only consider Boolean criteria that are either satisfied or not. Suppose a language where propositional variables x i ∈ {0, 1}, i = 1, . . . , n, encode criteria i ∈ P. An interpretation of x of the language corresponds to a Boolean alternative x for which criteria are fully satisfied or not. For simplicity, we use the same symbol x for the alternative and the corresponding interpretation. As usual x i will denote the case where x i = 1 and ¬x i the case where x i = 0. We denote by T x ⊆ P the set of criteria satisfied by alternative x. The subset T x is encoded by the interpretation ∧ i∈T x x i ∧ i / ∈T x ¬x i .

Fuzzy measures as possibilistic logic bases

First consider a Boolean fuzzy measure taking values on {0, 1}. For any focal set T ∈ F , it is clear that ∀A ⊂ T, ( A) = 0 and ∀A ⊇ T, (A) = 1. Consider an alternative x ∈ {0, 1} n . In the decision context, a Boolean fuzzy measure means groups of criteria are either fully important or not at all, so that for an alternative x to be acceptable, it is necessary and sufficient that all criteria in some focal set T of be jointly satisfied, i.e., ∧ i∈T x i = 1. The logical formula expressing the global acceptability of x is thus ≡ ∨ T ∈F ∧ i∈T x i which is a Boolean polynomial. By construction, no conjunction is redundant in this expression.

Putting this formula in conjunctive normal form, one obtains a logical base of clauses B that exactly describes the priority scheme expressed by the Boolean fuzzy measure, in terms of a conjunction of clauses of the form = ∨ j=1,. ..,k:i j ∈T j x i j , one per k-tuple of criteria, each criterion i j involved being taken in a different focal element T j . 3It is obvious that no such clause contains a negative literal. And we have that xB if and only if (T x ) = 1.

Example 2. We consider three criteria {1, 2, 3}, the evaluation scale L = {0, 1} and the following fuzzy measure:

∅ {1} {2} {3} {1, 2} {1, 3} {2, 3} {1, 2, 3} 0 0 0 1 1 1 1 1 # 0 0 0 1 1 0 0 0
We have F = {{1, 2}, {3}}, which corresponds to the formula = (x 1 ∧ x 2 ) ∨ x 3 = (x 1 ∨ x 3 ) ∧ (x 2 ∨ x 3 ). Hence the corresponding possibilistic logic N-base is B = {(x 1 ∨ x 3 , 1), (x 2 ∨ x 3 , 1)}. Now consider a fuzzy measure taking values on a totally ordered scale L. Recalling the fact that its Möbius transform # is a possibility distribution on 2 P , the fuzzy measure can be encoded as a -base, interpreting the basic possibility assignment # (T ) > 0 as the actual possibility degree of the conjunction of atoms corresponding to criteria in T.

The -base equivalent to the fuzzy measure is thus

B ( ) = {[∧ i∈T x i , # (T )], T ∈ F }. (1)
By construction, B N (x) = max T ∈F min(min i∈T x i , # (T )) = (T x ), from Proposition 1. It means that x is acceptable at least to degree if it satisfies all criteria in at least one of the focal sets of of importance level or greater, i.e. all criteria in some T such that # (T ) ≥ .

Using the transformation from the disjunctive to the conjunctive normal form, B ( ) can be rewritten as a set B N ( ) of prioritized positive clauses. To make this transformation, we can proceed by first rank-ordering the subset

# (F ) = { # (T ), T ∈ F } as 1 = 1 > 2 > • • • > > 0. Let F j = {T, # (T ) = j }. Then B ( ) = {[∨ T ∈F j ∧ i∈T x i , j ], i = 1, . . . , }.
Applying the results of Section 2.2, the N-base representing the fuzzy measure is (with convention +1 = 0):

B N ( ) = ∨ i j=1 ∨ T ∈F j ∧ k∈T x k , 1 -i+1 , i = 1, . . . , , noticing that N ({∨ T ∈F j ∧ i∈T x i : j = 1, . . . , i}) = 1 -i+1 ,
where N is the necessity measure associated to the possibility distribution # on the power set 2 P . It is clear that by construction,

B N (x) = B (x) = (T x ) = N (B N x ), where B N x = { i : ( i , i ) ∈ B N ( ), x ∈ M( i )}. Note that B N
x can always be expressed as a set of weighted disjunctions of positive literals.

Example 3. We consider three criteria {1, 2, 3}, the importance scale is L = {0 < 1 < 2 < 1}, where 2 = 1 -1 , and the following fuzzy measure:

∅ {1} {2} {3} {1, 2} {1, 3} {2, 3} {1, 2, 3} 0 2 1 0 2 1 2 1 # 0 2 1 0 0 1 2 0
Hence we have

F 1 = {{1, 3}}, F 2 = {{1}, {2, 3}}, F 1 = {{2}}, hence one directly gets B = {[ p 1 ∧ p 3 ], [ p 1 ∨ ( p 2 ∧ p 3 ), 2 ], [ p 2 , 1 ]}. Then, the corresponding possibilistic logic base B N ( ) is {( p 1 ∧ p 3 , 1 -2 ), (( p 1 ∧ p 3 ) ∨ p 1 ∨ ( p 2 ∧ p 3 ), 1 -1 ), ( p 1 ∧ p 3 ) ∨ p 1 ∨ ( p 2 ∧ p 3 ) ∨ p 2 , 1)
} and in clausal form, taking subsumption into account: 4As can be observed from the example, the possibilistic logic base B N ( ) reflects the conjugate c of fuzzy measure defined as

B N ( ) = {( p 1 , 1 -2 ), ( p 3 , 1 -2 ), ( p 1 ∨ p 3 , 1 -1 ), ( p 1 ∨ p 2 , 1)}.
c (A) = 1 -( A c ), where A c denotes the complement of A, namely c (A) = max T j ⊆A { : = ∨ j:i∈T j p i , ( , ) ∈ B N ( )}.
Such a representation of a fuzzy measure is unusual in multiple criteria aggregation. However, while the values of the fuzzy measure directly reflect the importance of groups of criteria, we obtain here another view of the interplay between criteria; namely ( i , i ) ∈ B N ( ) means that if all criteria in the disjunction i are violated, the resulting global evaluation cannot be above 1i .

For instance, the possibilistic base in the above example expresses that violating criteria '1' and '2' is forbidden as it leads to the full rejection of the considered alternative. Moreover, violating one of criteria '1' and '3' leads to a global evaluation not greater than 2 , while violating both of them leads to a global evaluation even worse, that is not greater than 1 , since 0 < 1 < 2 < 1. This result might look surprising since the fuzzy measure value of criterion '3' is 0.

But we should observe that, together, criteria '1' and '3' reach importance value 1, that is, if an alternative satisfies both criteria, it satisfies all formulas in B N ( ), and gets the maximal global rating.

Possibilistic logic bases as set functions

A set of formulas j , j = 1, . . . , m, in a language where propositional variables x i encode Boolean criteria i ∈ P can be viewed as requirements j ∈ R expressed as logical combinations of elementary criteria [START_REF] Dubois | Using possibilistic logic for modeling qualitative decision: ATMS-based algorithms[END_REF]. In such a context, an alternative x satisfies requirement j or not, according to whether it is or not a model of j . So using the characteristic function of M( j ), the acceptability of an alternative x according to each requirement j can be evaluated by computing I M( j ) (x). Now, using the possibility distribution over the models of a possibilistic logic base B N = {( j , j ) | j = 1, . . . , m} an associated set-function can be defined on 2 P . More precisely, when we consider a subset T of properties, it can be viewed as a subset T x associated to the Boolean alternative x T with x T i = 1 if i ∈ T and 0 otherwise. Hence we can formulate the following definition:

Definition 4. The set function B induced by B N is defined, for all T ⊆ P, by B (T ) = B (x T ) = ∧ i / ∈B N x T (1 -i ) where x T = ∧ i∈T x i ∧ i /
∈T ¬x i , and

B N x = { j : ( j , j ) ∈ B N , x ∈ M( j )}.
It is clear that since the fuzzy measure is obtained by means of the possibility distribution B induced by B N , replacing the latter by its deductive closure is immaterial in the determination of B .

Note that if we apply this definition to the N-base calculated from a fuzzy measure, it is obvious that we recover this fuzzy measure, that is, B N ( ) (T ) = (T ) (they correspond the same possibility distribution on interpretations). To illustrate this point, let us consider the N-base obtained in the previous example and let us calculate the associated fuzzy measure.

Example 4. We consider three criteria {1, 2, 3}, the scale L = {0 < 1 < 2 < 1}, where 2 = 1 -1 , and the possibilistic logic base

B N = {(x 1 , 1 -2 ), (x 3 , 1 -2 ), (x 1 ∨ x 3 , 1 -1 ), (x 1 ∨ x 2 , 1)}. Let 1 = x 1 , 2 = x 3 , 3 = x 1 ∨ x 3 and 4 = x 1 ∨ x 2 .
Let us calculate the associated fuzzy measure for all the subsets of criteria.

The set A

The associated alternative x

B N x (A) = N (B N x ) {1, 2, 3} (1, 1, 1)
{ 1 , 2 , 3 , 4 } 1 {1, 2} (1, 1, 0) { 1 , 3 , 4 } 2 {1, 3} (1, 0, 1) { 1 , 2 , 3 , 4 } 1 {2, 3} (0, 1, 1) { 2 , 3 , 4 } 2 {1} (1, 0, 0) { 1 , 3 , 4 } 2 {2} (0, 1, 0) { 4 } 1 {3} (1, 1, 1) { 2 , 3 } 0
The obtained fuzzy measure is the fuzzy measure used in the previous example.

While the N-base obtained from a fuzzy measure contains only positive clauses, the set function B obtained from any possibilistic logic base B N is not always a fuzzy measure since some clauses j in an N-base may contain negated terms. This feature accounts for a kind of negative synergy between properties, that can be expressed using a possibilistic logic description of acceptability requirements.

Example 5. We consider three properties {1, 2, 3}, the scale L = {0 < 1 < 1}, where 1 = 1 -1 , and the N-base B = {(x 1 , 1), (x 2 ∨ x 3 , 1), (x 2 , 1 -1 ), (¬x 2 ∨ ¬x 3 , 1)}.

Let 1 = x 1 , 2 = x 2 ∨ x 3 , 3 = x 2 and 4 = ¬x 2 ∨ ¬x 3 . It means that it is imperative to satisfy criterion 1, but criteria 2 and 3 must be neither both satisfied nor both violated, and violating criterion 2 leads to a global evaluation not greater than 1 -1 .

Let us calculate the set-function . The reader can check it is not a fuzzy measure.

T x x B N x (T x ) = B (x) = N (B N x ) {1, 2, 3} (1, 1, 1) { 1 , 2 , 3 } 0 {1, 2} (1, 1, 0) { 1 , 2 , 3 , 4 } 1 {1, 3} (1, 0, 1) { 1 , 2 , 4 } 1 {2, 3} (0, 1, 1) { 2 , 3 } 0 {1} (1, 0, 0) { 1 , 4 } 0 {2} (0, 1, 0) { 2 , 3 , 4 } 0 {3} (1, 1, 1) { 2 , 4 } 0
In order to obtain a fuzzy measure, the set function B has to satisfy the properties B (∅) = 0, B (P) = 1 and S ⊆ T entails B (S) ≤ B (T ). When we consider a Boolean alternative x, does not follow from B N

x whenever has the form ∨ i∈I ¬x i ∨ ∨ j∈J x j where I ⊆ T x and J ⊆ T x c where T x c is the complement of T x . So, as

N (B N x ) = ∧ i / ∈B N x (1 -i ) = B (T x
) we can identify the properties a possibilistic logic base needs to have in order to be associated to a fuzzy measure. Proposition 3. The following equivalences hold, given an N-base B N in clausal form:

• B (P) = 1 if and only if B N /
(∨ i∈I ¬x i , ), ∀I ⊆ {1, . . . , m}, ∀ > 0. • B (∅) = 0 if and only if there exists a subset J of {1, . . . , m} and a clause = ∨ j∈J x j such that B N ( , 1).

• ∀S ⊆ T , B (S) ≤ B (T ) if and only if ∀S ⊆ T, max j / ∈B N x T j ≤ max i / ∈B N x S i .
Proof. The first equivalence: x P = (1, 1, . . . , 1) = ∧ i∈P x i . B (P) = 1 if and only if x P satisfies all formulas in B N . But the clauses violated by x P are all of the form ∨ i∈I ¬x i for some non-empty set I of variables. Hence the result.

The second equivalence: x ∅ = (0, 0, . . . , 0) = ∧ i∈P ¬x i . B (∅) = 0 if and only if x ∅ violates at least one formula of priority 1 in B N . But the clauses violated by x ∅ are all of the form ∨ i∈I x i for some non-empty set I of variables. So

i / ∈B N x S (1 -i ) ≤ ∧ i / ∈B N x T (1 -i ) which is equivalent to ∨ i / ∈B N x T i ≤ ∨ i / ∈B N x S i . ç
N = {(x 1 , 1 -2 ), (x 3 , 1 -2 ), (x 1 ∨ x 3 , 1 -1 ), (x 1 ∨ x 2 , 1)}.
• There are no formulas with negation so (P) = 1.

• The logical formula (x 1 ∨ x 2 , 1) entails (∅) = 0. • {1} ⊆ {1, 2} : ∨ i / ∈B N x {1,2} i = 1 -2 = ∨ i / ∈B N x {1} ; {1} ⊆ {1, 3} : ∨ i / ∈B N x{1,3} i = 0 ≤ ∨ i / ∈B N x {1} i = 1 -2 ; {3} ⊆ {1, 3} : ∨ i / ∈B N x {1,3} i = 0 ≤ ∨ i / ∈B N x {1} i = 1.
So the possibilistic logic base is associated to a fuzzy measure.

Next, consider the possibilistic logic base of Example 5:

B N = {(x 1 , 1), (x 2 ∨ x 3 , 1), (x 2 , 1 -2 ), (¬x 2 ∨ ¬x 3 , 1)}. We have ∨ i / ∈B N x {1,2,3} i = 1 > ∨ i / ∈B N x {1,2}
i = 0 so B is not associated to a fuzzy measure.

The question raised by Proposition 3 has to do with monotone Boolean functions. First, in the classical case, a set of requirements encoded as a standard propositional knowledge base B is equivalent to a Boolean function whose arguments are Boolean attributes x i taking values 0 or 1 according to whether the alternative is acceptable or not. The (increasing) monotonicity of the corresponding set-function B is equivalent to the monotonicity of the Boolean function. And it is known that a Boolean function is monotone if and only its reduced disjunctive normal form contains only 0, 1 and positive literals. It corresponds to the associated -base. The conjunctions of literals in this form here correspond to focal elements of B .

In the more general case, the third point of Proposition 3 is not easy to interpret. However, based on the above results for the Boolean case, one may say that the monotonicity of the set-function B induced by the N-base B N is easier to check on the equivalent -base B . Let 1 > 2 > • • • > k be the distinct weights appearing in B , and B i be the -base containing all terms with weight i . Then B will be monotone if and only if all Boolean functions associated to the subbases B i are monotone, that is, if each B i , put in non-redundant form, contains only conjunctions of positive literals (corresponding to the qualitative Möbius transform of B ). In other words, an N-base B N induces a monotonic set-function if and only if it is logically equivalent to another N-base where no negative literal appears. While this formulation is easier to understand than the third condition of Proposition 3, the latter is easier to automatically check in practice.

Sugeno integrals and possibilistic logic bases

Let (x) be a Sugeno integral based on a fuzzy measure and a tuple x of local evaluations which both take their values in a finite totally ordered scale L. In the previous section, assuming x is Boolean, we have shown how to compute (x) as the degree of satisfaction of a possibilistic knowledge base by an interpretation of the language generated by the Boolean attributes x i . In that case, (x) = (T x ) and the Sugeno integral coincides with a fuzzy measure.

In this section we are going to generalize the previous results concerning fuzzy measures to Sugeno integrals when attributes are no longer Boolean. More precisely, we are going to present how to encode a Sugeno integral by means of a possibilistic logic base and how some possibilistic logic bases can be interpreted as a Sugeno integral.

From Sugeno integrals to possibilistic logic bases

The starting point is to turn a Sugeno integral into a -base, based on the fact that the expression of the former in terms of the qualitative Möbius transform (x) = max T ⊆F min( # (T ), min i∈T x i ) is similar to the expression of the possibility distribution of a -base B ( ) = {[∧ j∈T j , # (T )] : T ∈ F }, except that in the latter, j is Boolean, while in min i∈T x i , x i ∈ L. So we must express an alternative x in terms of weighted Boolean alternatives.

For each criterion i, we define |L| -1 predicates p i ( ), where 0 ∈ L with the following convention: p i ( ) is true if and only if x i ≥ . In the previous section, where x is Boolean, p i (1) was simply denoted by the atom x i . Note that we can restrict the scope of p i ( ) to > 0 since, under our convention, p i (0) is a tautology (and thus is not equivalent to ¬x i in the previous section). We thus consider a simple first order language L with atoms { p i ( ) : i = 1, . . . , n; > 0 ∈ L}, and connectives of negation, conjunction and disjunction. Moreover, we have the following set of domain axioms: ٛ p i ( ) ∨ ¬ p i ( ), ∀ > > 0, i = 1, . . . , n. This language will be interpreted in the set of alternatives x ∈ L P . We define the satisfaction relation as follows: An alternative x = (x 1 , . . . , x n ) clearly satisfies the formula ∧ n i=1 p i (x i ), and can be viewed as the Boolean interpretation ∧ n i=1 (∧ ≤x i p i ( ))∧(∧ >x i ¬ p i ( )). A logical rendering of the Sugeno integral of x with respect to a fuzzy measure will rely on the use of -possibilistic logic formulas as follows. Each term min( # (T ), min i∈T x i ) is encoded by the -base

• x p i ( ) if

B

  (∅) = 0 if and only if B N contains at least one such formula with priority 1. The third equivalence: ∀S ⊆ T ∈ P, B (S) ≤ B (T ) if and only if ∀S ⊆ T , N (B N x S ) ≤ N (B N x T ). The latter reads ∧

Example 6 .

 6 First let us consider the possibilistic logic base of Example 4: B

  B T ( ) = {[∧ i∈T p i ( ), ] : ≤ # (T )} Lemma 1. B T ( ) (x) = min( # (T ), min i∈T x i ) Proof. B T ( ) (x) = max ≤ # (T ) min( , min i∈T I M( p i ( )) (x)).

  and only if x i ≥ ; • x¬ p i ( ) if and only if x i < ; • x ∧ if and only if x and x ; • x ∨ if and only if x or x .

It is a fully revised and extensively rewritten version of a workshop paper[START_REF] Dubois | A possibilistic logic view of Sugeno integrals[END_REF] with new results.

By construction, no such clause is redundant.

This base can be more simply written as {( p 1 , 1 ), ( p 3 , 1 ), ( p 1 ∨ p 3 , 2 ), ( p 1 ∨ p 2 , 1)}, since 1 = 1 -2 . But we prefer to keep the notation 1-so as to lay bare the duality between -and N-bases.

Note that I M( p i ( )) (x) = 0 as soon as > x i , and the term min( , I M( p i ( )) (x)) is subsumed by (i.e., less than) min(x i , I M( p i (x i )) (x)) = x i if ≤ x i . Now,

• either # (T ) ≤ x i , ∀i ∈ T and then I M( p i ( # (T ))) (x)) = 1, ∀i ∈ T , hence B T ( ) (x) = # (T ); • or # (T ) > min i∈T x i , and then min i∈T I M( p i ( )) (x)) = 0, ∀ such that min i∈T x i < ≤ # (T ), hence B T ( ) (x) = min i∈T x i . ç

Then we easily derive the following result, making the union of the bases B T ( ), one for each focal set T in F :

Proposition 4. The -base B ( ) = T ∈F B T ( ) encodes the Sugeno integral (x), that is:

Proof. This is obvious since B 1 ∪B 2 = max( B 1 , B 2 ) for -bases. ç

However, B ( ) is large and contains redundant formulas. Instead of building one base per focal set, one may proceed levelwise, building one base per value in the scale L, and considering the inequalities (x) ≥ i for each i ∈ L. Let us begin with a formal characterization of tuples x that satisfy this inequality.

Proposition 5.

(x) ≥ if and only if ∃T ∈ F s.t. # (T ) ≥ and ∀i ∈ T, x i ≥ .

Proof. Let us use again the identity (x) = max T ∈F min( # (T ), min i∈T x i ). Then clearly, (x) ≥ if and only if ∃T ∈ F , min( # (T ), min i∈T x i ) ≥ . For such a focal set T, the condition # (T ) ≥ must hold, as well as min i∈T x i ≥ , i.e. ∀i ∈ T, x i ≥ must be satisfied. ç

This easy result says that x is evaluated at least at level if and only if it satisfies to degree at least all criteria of a focal set having importance at least . In fact, it is clear that we only need the smallest focal elements in the sense of inclusion among those such that # (T ) ≥ . Denote them by F = min ⊆ {T : # (T ) ≥ } (they are the focal sets of the Boolean set function (T ) = 1 if and only if (T ) ≥ ). Then Proposition 6.

(x) ≥ if and only if ∃T ∈ F , ∀i ∈ T, x i ≥ .

We can then characterize the set of objects x such that (x) ≥ , as the set of interpretations of

Note that this base does not contain formulas [∧ i∈T p i ( ), 1], T ∈ F for which ∃S ⊂ T such that S ∈ F as per Proposition 6, i.e., it contains no redundant formula. B ( ) is actually the Boolean formula ∨ T ∈F ∧ j∈T p j ( ).

The -base B ( ), constructed from each focal set of is logically equivalent to the union B ↑ ( ) = {[∧ j∈T p j ( ), ] : ∀T ∈ F , ∀ > 0 ∈ L} of all B ( ) after formulas are assigned weight . B ↑ ( ) is obtained from B ( ) after removing the redundant weighted clauses in the latter. The main result of this section then follows easily:

Proof.

(x) = max ∈L min( , I (x)≥ (x)) = max ∈L min( , B ( ) (x)), due to Proposition 7, which is B ↑ ( ) (x). Then use Proposition 4. ç

The -base B ↑ ( ) is not redundant by construction. Indeed, if it were, there would be two cubes in it of the form [∧ j∈T p j ( ), ], [∧ j∈S p j ( ), ] such that T ⊆ S and ≤ , where S ∈ F , T ∈ F . But this is impossible as, if = and T S, then S cannot be a focal set of , and < is incompatible with T ⊆ S.

The minimal -base B ↑ ( ) can be turned into an N-base if needed, using the technique presented in Section 2. This transformation is clearly equivalent to the change from a maxmin expression of Sugeno integral to a minmax expression as appears in Proposition 1. Note that in case of binary alternatives, identifying p i (1) to atoms x i we recover the -possibilistic base B ( ) identified in the previous section (Eq. ( 1)).

Example 7. We consider three criteria P = {1, 2, 3} and the evaluation scale L = {1, 2 , 1 , 0} with 1 > 2 > 1 > 0. We consider a Sugeno integral with respect to defined by ({1})

is associated to the following qualitative Möbius transform:

Proceeding by levels:

for any x greater than ( 1 , 0, 0) or (0, 1 , 0) or (0, 0, 1 ).

i.e., for any x greater than (0, 0, 2 ) satisfies (x) ≥ 2 .

• We want to find the alternatives x such that (x) = 1. It is clear that

so all x greater than (1, 0, 1) satisfy (x) = 1. It corresponds to the following -possibilistic logic base:

It is the one we obtained after deleting redundant cubes in B ( ). So, the Sugeno integral can be interpreted as follows:

• An object that satisfies properties 1 and 3 to degree 1 is fully satisfactory.

• An object that satisfies property 3 to at least level 2 is satisfactory at least to degree 2 .

• An object that satisfies any of properties 1-3 to degree 1 is satisfactory at least to degree 1 .

From -bases to Sugeno integrals

Consider a -possibilistic base similar to the one obtained in the previous subsection,

. . , k} we want to identify the class of fuzzy measures such that B (x) = (x).

First we try to find the class of fuzzy measures induced by one logical formula [∧ j∈T p j ( ), ]. It is clear that ∀x, [∧ j∈T p j ( ), ] (x) ≤ . Hence we just need to identify the fuzzy measures such that [∧ j∈T p j ( ), ] (x) ≥ . In order to calculate these solutions, let us make a brief reminder of the result proved in [START_REF] Rico | Preference modeling on totally ordered sets by the Sugeno integral[END_REF].

We consider the equation (x) ≥ for a fixed x. First we denote by A ≥ x, the set of criteria whose evaluation in x is greater than or equal to and the following fuzzy measure:

Hence the following result can be proved [START_REF] Rico | Preference modeling on totally ordered sets by the Sugeno integral[END_REF]:

In our context we consider k inequalities induced by the -bases of the form (x i ) ≥ i , where x i j = i if j ∈ T i and 0 otherwise. The set of solutions is { :

Example 8. Let us consider the following possibilistic logic base and let us calculate the associated Sugeno integral:

We want to find such that (0, 0, 1 ) ≥ 1 , (0, 1 , 0) ≥ 1 , ( 1 , 0, 0) ≥ 1 , (0, 0, 2 ) ≥ 2 and (1, 0, 1) ≥ 1. We obtain the following fuzzy measures: ∀A ⊂ P, 1 = ˇ (0,0, 1 ), 1 (A) = 1 if {3} ⊆ A, and 0 otherwise; 2 = ˇ (0, 1 ,0), 1 (A) = 1 if {2} ⊆ A, and 0 otherwise; 3 = ˇ ( 1 ,0,0), 1 (A) = 1 if {1} ⊆ A, and 0 otherwise; 4 = ˇ (0,0, 2 ), 2 (A) = 2 if {3} ⊆ A, and 0 otherwise; 5 = ˇ (1,0,1),1 (A) = 1 if {1, 3} ⊆ A, and 0 otherwise. So the solutions are fuzzy measures greater than ∨ 5 i=1 i whose values are given in the following table:

We retrieve the fuzzy measure we started with in the previous example.

Note that if we start from any -base, we just need to

• put B in disjunctive normal form, that is, put each formula containing only positive literals of the form p i ( ), such that [, ] ∈ B as a non-redundant disjunction of conjunctions of literals ∨ i=1 ∧ j∈T i p i ( ); • create weighted products [∧ j∈T i p i ( ), ];

• delete subsumed weighted products.

Then the fuzzy measure is such that its qualitative Möbius transform is defined by # (T i ) = for all weighted products ∧ j∈T i p i ( ).

Related work

There do not exist many works trying to provide a logical reading of decision processes. In decision under uncertainty, let us mention a logical approach [START_REF] Dubois | Using possibilistic logic for modeling qualitative decision: ATMS-based algorithms[END_REF] where uncertain knowledge and prioritized preference are represented by means of two distinct possibilistic logic N-bases, and where the pessimistic or optimistic decision criteria that are maximized are particular cases of Sugeno integrals. In [START_REF] Benferhat | Bipolar possibility theory in preference modeling: representation, fusion and optimal solutions[END_REF], a multicriteria decision problem is expressed in terms of prioritized constraints and wishes, where constraints are modelled by an N-base, and wishes by a -base, handled separately in the decision process; however the latter is not interpreted as an N-based put in disjunctive form. In [START_REF] Gérard | Ranking alternatives on the basis of generic constraints and examples-a possibilistic approach[END_REF], in a multiple criteria decision perspective, a qualitative approach, also in the spirit of possibilistic logic, is compared to a counterpart of a Choquet integral-based aggregation process. However, the closest related work is [START_REF] Greco | Axiomatic characterization of a general utility function and its particular cases in terms of conjoint measurement and rough-set decision rules[END_REF] in which Greco et al. show that the set of alternatives for which a Sugeno integral is less than a given score can be described by means of if-then rules.

More precisely, Greco et al. consider a slightly different setting from the one in this paper. Let us give a brief refresher of their result.

Let us begin with the notations. For each i ∈ P, L i is the set of ratings of alternatives with respect to criteria i. The set of alternatives is thus X = n i=1 L i . On X there is a comprehensive weak preference relation . For all x, y ∈ X x y means x is at least as good as y. Its asymmetric part is denoted by ≻.

In such a context, there exists the following link between the Sugeno integral representation and a set of decision rules (after Theorem 3 in [START_REF] Greco | Axiomatic characterization of a general utility function and its particular cases in terms of conjoint measurement and rough-set decision rules[END_REF]): Proposition 10. A preference relation on X is representable by a Sugeno integral if and only if there exist

• a set of decision rules, called single-graded, of the form "if g i 1 (x i 1 ) ≥ g(y), . . . , g i k (x i k ) ≥ g(y), then x y", where {i 1 , . . . , i k } ⊆ {1, . . . , n} such that

• each z ∈ X such that z y satisfies the antecedent of at least one rule whose consequent is "then x w" where w y; • each z ∈ X such that ¬(z y) does not satisfy the antecedent of any rule whose consequent is "then x w" with w y;

• if the decision rule: "if g i 1 (x i 1 ) ≥ g(y), . . . , g i k (x i k ) ≥ g(y) then x y" holds, then for any w ∈ X such that g(y) ≥ g(w), the decision rule "if g i 1 (x i 1 ) ≥ g(w), . . . , g i k (x i k ) ≥ g(w) then x w" also holds.

In a nutshell, the result explains that the decision rules representable by a Sugeno integral are only single-graded rules, i.e., that involve a single threshold g(y). But Greco et al. [START_REF] Greco | Axiomatic characterization of a general utility function and its particular cases in terms of conjoint measurement and rough-set decision rules[END_REF] do not provide an explicit representation of a Sugeno integral in N-based, or -based possibilistic logic.

Similar to our work, Greco et al. consider sets of the form {x| (x) ≥ }. More precisely, for an alternative x and a real number , the rules proposed by Greco et al. can thus be expressed as follows, letting = g(y) for some fixed option y. Let A(x, ) be the set of criteria on which x is better or equal to :

Let us note that using the results presented in [START_REF] Rico | Preference modeling on totally ordered sets by the Sugeno integral[END_REF] the previous condition is necessary and sufficient.

In this paper, we have shown that a Sugeno integral can be modeled by a -base or an N-base in possibilistic logic. What the above remarks show is that each single-graded rule in the sense of Greco et al. can thus be viewed as a weighted formula of the form [∧ j∈ i p j ( ), ] in the obtained -base (however the conclusion part of their rules is obtained in our setting by computing the possibility degree of the corresponding alternative, instead of concluding on a pairwise comparison of alternatives). What this paper lays bare is that the g(y) values appearing in each singlegraded rule of Greco et al. can be restricted to qualitative Möbius transform weights associated to the set of criteria appearing in the condition part of the rule. In the future, we shall consider encoding single-graded rules of the form "if g i 1 (x i 1 ) ≤ g(y), . . . , g i k (x i k ) ≤ g(y), then x y", directly in N-based possibilistic logic, using the min-max expression of Sugeno integral (that appears in Proposition 1).

Concluding remarks

Any set of logical formulas not involving negation can be represented by a Boolean polynomial. Sugeno integrals are lattice polynomials obeying boundary conditions. It is then natural to look for a logical description of Sugeno integrals. As the latter involve constants in a totally ordered set, the natural target language is possibilistic logic. This paper has demonstrated this connection in detail and pointed out the relationship with the rule-based representation of Sugeno integrals. The search for a logical account of fuzzy measures is not fully carried out yet, though. The proposed translation enables assertions of the form (x) ≥ to be verified via a kind of model-checking problem (verify whether an interpretation x satisfies a prioritized knowledge base). But it does not allow to represent such assertions at the syntactic level and reason about them. This task may request the use of generalized possibilistic logic [START_REF] Dubois | Generalized possibilistic logic[END_REF], and probably its extension where the semantics of formulas is in terms of families of fuzzy measures.


Touch the map! Designing Interactive Maps for Visually

Impaired People

Open Archive TOULOUSE Archive Ouverte (OATAO)

OATAO is an open access repository that collects the work of Toulouse researchers and makes it freely available over the web where possible. Any correspondance concerning this service should be sent to the repository administrator: staff-oatao@listes-diff.inp-toulouse.fr

  This is an author-deposited version published in : http://oatao.univ-toulouse.fr/ Eprints ID : 12370

	To link to this article : DOI :10.1145/2444800.2444802
	URL : http://dx.doi.org/10.1145/2444800.2444802
	To cite this version : Brock, Anke Touch the map! Designing
	Interactive Maps for Visually Impaired People. (2013) ACM
	SIGACCESS Accessibility and Computing (n° 105). pp. 9-14. ISSN
	1558-2337


Amplitude Independent Frequency Synchroniser for a Cubic Planar Polynomial System Islam Boussaada

Keywords: Mathematics Subject Classification (2010). Primary 34C15, 34C25, 34C37 Frequency synchronization, Amplitude independent, Center conditions, Period function, Normal forms, Isochronicity, Linearizability, Polynomial systems, Symbolic computations, Gröbner basis, FGb algorithm, Maple

, also it can be considered as an adaptation of a qualitative theory method to a synchronization problem.

Introduction

We consider the planar dynamical system, dx dt = ẋ = X(x, y), dy dt = ẏ = Y (x, y), (1.1) where (x, y) belongs to an open connected subset U ⊂ R 2 , X, Y ∈ C k (U, R), and k ≥ 1. Due to Poincaré : an isolated singular point p ∈ U of (1.1) is a center if and only if there exists a punctured neighborhood V ⊂ U of p such that every orbit in V is a cycle surrounding p. A center is said to be isochronous if all the orbits surrounding it have the same period. An overview of J.Chavarriga and M.Sabatini [START_REF] Chavarriga | A survey of isochronous centers[END_REF] present the methods and basic results concerning the problem of the isochronicity, see also [START_REF] Franc ¸oise | Isochronous Systems and Perturbation Theory[END_REF][START_REF] Chouikha | Isochronous centers of Lienard type equations and applications[END_REF][START_REF] Bardet | Compexity reduction of C-algorithm App[END_REF][START_REF] Boussaada | Isochronicity conditions for some planar polynomial systems[END_REF][START_REF] Bardet | Isochronicity conditions for some planar polynomial systems II[END_REF]. Synchronization problem consists in bringing appropriate modifications on a given system to obtain a desired dynamic, see [START_REF] Pikovsky | Synchronization: A Universal Concept in Nonlinear Sciences[END_REF][START_REF] Blekhman | Synchronisation in Science and Technology[END_REF]. Along this paper, the desired phase portrait contains a compact region around a singular point at the origin in which lies periodic orbits with the same period (independently from the chosen initial conditions which is not always the case). More concretely, in this paper we consider the following problem; Starting from a non isochronous polynomial planar system, are there any polynomial perturbation which insures the local linearisability of the perturbed system. In this paper we adopt the normal forms method often used in qualitative theory investigations; center-focus problem, bifurcation problem and local linearisability problem. The problem of local linearisability conditions of of the planar linear center perturbed by cubic nonlinearities (in all generalities on the system parameters 14 parameters) is far to be solved.

In this paper, starting from a 5-parameters non isochronous Chouikha cubic system [START_REF] Chouikha | Isochronous centers of Lienard type equations and applications[END_REF], we identify all possible monomial perturbations of degree d ∈ {2, 3} insuring local linearizability of the perturbed system. Investigations are based on the normal forms Theory.

In the following system as well as in all other considered systems, all parameters are reals. Consider the real Liènard Type equation

ẍ + f (x) ẋ2 + g(x) = 0 (1.2)
or equivalently its associated two dimensional (planar) system

ẋ = y ẏ = -g(x) -f (x)y 2 (1.
3)

The study of isochronicity of (1.2) was established first in M. Sabatini paper [START_REF] Sabatini | On the period function of x + f (x)x 2 + g(x) = 0[END_REF]. The sufficient conditions of the isochronicity of the origin O for system (1.3) with f and g of class C 1 are given. In the analytic case, the necessary and sufficient conditions for isochronicity are given by A.R.Chouikha in [START_REF] Chouikha | Isochronous centers of Lienard type equations and applications[END_REF]. In the same paper, the author implemented a new algorithmic method for computing isochronicity conditions for system (1.3) called C-algorithm. As an application of this algorithm, the author studied the following cubic system ẋ = -y + ã1,2,1 x 2 y ẏ = x + ã2,2,0 x 2 + ã2,0,2 y 2 + ã2,3,0 x 3 + ã2,1,2 xy 2 (1.4) where all the parameters values for which system (1.4) has an isochronous center at the origin are established in the following theorem. We note that the coefficient a i,j,k denotes the parameter of the monomial perturbation of the i th equation of the linear isochronous center ( ẋ = -y, ẏ = x) of degree j in x and of degree k in y Theorem 1.1 (Chouikha,[START_REF] Chouikha | Isochronous centers of Lienard type equations and applications[END_REF]). System (1.4) has an isochronous center at 0 if and only if its parameters satisfy one of the following conditions

1. ã2,3,0 = -(2/3)ã 1,2,1 , ã2,1,2 = 3ã 1,2,1 , ã2,2,0 = ã2,0,2 = 0 2. ã2,1,2 = ã1,2,1 , ã2,2,0 = ã2,3,0 = ã2,0,2 = 0 3. ã2,3,0 = (1/14)ã 2 2,0,2 , ã2,1,2 = (3/7)ã 2 2,0,2 , ã1,2,1 = (1/7)ã 2 2,0,2 , ã2,2,0 = -(1/2)ã 2,0,2 4. ã2,1,2 = ã2 2,0,2 , ã2,3,0 = 0, ã1,2,1 = (1/2)ã 2 2,0,2 , ã2,2,0 = -(1/2)ã 2,0,2 .
A 1-parameter perturbation of system (1.4) is studied in [START_REF] Chouikha | Chen Isochronicity of analytic systems via Urabe's criterion[END_REF]. Namely, the following system

ẋ = -y + a 1,1,1 xy + a 1,2,1 x 2 y ẏ = x + a 2,2,0 x 2 + a 2,0,2 y 2 + a 2,3,0 x 3 + a 2,1,2 xy 2 (1.5)
which is system (1.4) perturbed by the underlined term. All the values of the parameters for which the above system (1.5) has an isochronous center at the origin were found.

Note that the above system stills reducible to the Liénard type equation for wich C-algorithm is applicable, see [START_REF] Boussaada | Isochronicity conditions for some planar polynomial systems[END_REF]. Section 2 is devoted to recall the head lines of the methodology of the Normal Forms algorithm, called in the sequel NF algorithm, which will allow us to obtain isochronicity necessary conditions.

The last section is concerned with the main result, which is an application of the NF method. Indeed, we consider an unknown 1-directional monomial perturbation of degree two or three of the system (1.4), namely

ẋ = -y + a 1,2,1 x 2 y + Ψ 1 (x, y) ẏ = x + a 2,2,0 x 2 + a 2,0,2 y 2 + a 2,3,0 x 3 + a 2,1,2 xy 2 + Ψ 2 (x, y) , (1.6)
in which only one of the monomials

Ψ 1 or Ψ 2 is non zero monomial (Ψ 1 Ψ 2 = 0) of degree d ∈ {2, 3}.
The problem turns to study eight polynomial cubic systems which are not reducible by the transformations described in [START_REF] Boussaada | Isochronicity conditions for some planar polynomial systems[END_REF] to Liénard type equation. For each system, we identify the values of the parameters for which the singular point at thea origin is an isochronous center. Hence it is done for (1.6).

The normal forms method

The normal form theory which is due essentially to Poincaré, presents a basic tool in understanding the qualitative behavior of orbit structures of a vector field near equilibria [START_REF] Guckenheimer | Nonlinear oscillations, dynamical systems, and bifurcation of vector fields[END_REF]. It was used for the study of center conditions and the nature of bifurcation of a given vector field. We also recall a pioneer work in this field established by Pleshkan (see [START_REF] Pleshkan | A new method of investigating the isochronicity of a system of two differential equations[END_REF]), in which the author presented an investigation method of isochronicity in the case of linear center perturbed by homogeneous cubic nonlinearity. The principle of Pleshkan's algorithm is very close to the one presented in Algaba et.al paper [START_REF] Algaba | Isochronicity via normal form[END_REF], where the normal form theory is used in the analysis of isochronicity and gave a recursive method for the isochronicity investigation. In the last cited paper, the autors studied cubic Liénard equation and obtained a characterization of the reversible Liénard equation having an isochronous center at the origin.

Let

x = (x 1 , x 2 ) ∈ R 2 and f (x 1 , x 2 ) ∈ R[x 1 , x 2 ] × R[x 1 , x 2 ]
and consider the general planar system

ẋ = Lx + f (x) = Lx + f 2 (x) + f 3 (x) + . . . + f k (x) + . . . , (2.1)
where Lx represents the linear part, L the Jacobian matrix associated to system (2.1) and f k (x) denotes the k th order vector homogeneous polynomials of x. We assume that the system admits an equilibrium at the origin O. The essential idea of the Normal Form theory is to find a near identity transformation

x = y + h(y) = y + h 2 (y) + h 3 (y) + . . . + h k (y) + . . . , (2.2)
by which the resulting system ẏ = Ly + g(x) = Ly + g 2 (y) + g 3 (y) + . . . + g k (y) + . . . ,

becomes as simple as possible. In this sense, the terms that are not essential in the local dynamical behavior are removed from the analytical expression of the vector field. Let us denote by h k (y) and g k (y) the k th order vectors homogeneous polynomials of y. According to Takens normal form theory, we define an operator as follows:

L k : H k → H k , U k ∈ H k → L k (U k ) = [U k , u 1 ] ∈ H k (2.4)
where u 1 = Ly is the linear part of the vector field and H k denotes a linear vector space containing the k th degree homogeneous vector polynomials of y = (y 1 , y 2 ). The operator [., .] is called the Lie Bracket, defined by

[U k , u 1 ] = LU k -D(U k )u 1
where D denotes the frechet derivative. Next, we define the spaces R k and K k as the range of L k and the complementary space of R k respectively. Thus, H k = R k + K k and one can then choose bases for K k and R k . The normal form theorem determines how it is possible to reduce the analytic expression of the vector field (see Gukenheimer-Holmes [START_REF] Guckenheimer | Nonlinear oscillations, dynamical systems, and bifurcation of vector fields[END_REF]). The authors give explicitly an analysis for the quadratic and the cubic cases. Consequently, a vector homogeneous polynomial f k ∈ H k can be split into two parts, such that one of them can be spanned in K k and the remaining part in R k .

Normal form theory shows that the part belonging to R k can be eliminated and the remaining part can be retained in the normal form. By the equations (2.1), (2.2) and (2.3), we can obtain algebraic equations one order after another.

Theorem 2.1 (Yu et. al.,[START_REF] Yu | Normal forms of vector field with perturbation parameters and their application[END_REF]). The recursive formula for computing the normal form coefficients and the nonlinear transformation are given by :

g k = f k + [h k , Ly] + k-1 i=2 (Df i h k-i+1 -Dh k-i+1 g i ) + [k/2] i=2 1 i! k-i j=i D i f j l1+l2+...+li=k-(j-i) 2≤l1,l2,...,li≤k+2-(i+j) h l1 h l2 . . . h li ,
for k = 2, 3, . . . see also [START_REF] Yu | Bi Symbolic computation of normal forms for semi-simple case[END_REF][START_REF] Yu | Computation of normal forms via a perturbation technique[END_REF]. System (2.3) can be transformed to the polar coordinate system with y 1 = rcos(θ), y 2 = rsin(θ) so that

ṙ = N j=1 α 2j+1 r 2j+1 + O(r 2N +3 ), θ = 1 + N j=1 β 2j+1 r 2j + O(r2N + 2). (2.5)
Recall that a necessary condition to have a center at the origin is that all the focal values α 2j+1 vanish. By the Hilbert's basis theorem, the set of focal values has a finite basis in the ring of polynomials in the coefficients of the initial system (2.1). Since the non vanishing of one of the angular component coefficient implies dependency of an associated period constant, a necessary condition for which this center is isochronous is that β 2j+1 vanish.

Recall that our study is motivated by the interest of describing a synchronizer for a desired dynamic but also to underline the key role that can the classification of centers and isochronous centers of polynomial systems have in applications such that synchronization problems.

Main results : Applications of the NF algorithm to cubic systems

In our study, we use Maple. To compute the Gröbner basis of the obtained polynomial equations in the ring of characteristic 0, we employ the Salsa Software [START_REF] Faugère | FGb Salsa Software[END_REF]. More precisely we use the FGb algorithm which is the most efficient algorithm in computing Gröbner basis [START_REF] Becker | Gröbner bases[END_REF], at least for the polynomial systems studied in this paper. We note also that we have used DRL ordering in all computations established in this paper.

Since our approach in investigation of isochronicity conditions is based on an algorithmic method, then we can guess that every simplification is beneficial in the goal of speeding the computations and reducing the necessary memory size. Solving multivariate algebraic equations (real polynomials) can be a very hard task if we try to manipulate the polynomial equations without tricks. Interested readers can find in the website of Salsa Software [START_REF] Faugère | FGb Salsa Software[END_REF], more precisely the page of J.C.Faugère, some important rules in solving polynomial systems and about Gröbner basis.

Let us consider the more general cubic perturbation of linear center :

ẋ = y + a 1,2,0 x 2 + a 1,0,2 y 2 + a 1,1,1 xy + a 1,3,0 x 3 + a 1,2,1 x 2 y + a 1,1,2 xy 2 + a 1,0,3 y 3 ẏ = -x + a 2,2,0 x 2 + a 2,0,2 y 2 + a 2,1,1 xy + a 2,30 x 3 + a 2,2,1 x 2 y + a 2,1,2 xy 2 + a 2,0,3 y 3 (3.1)
or equivalently the following one :

ẋ = -y + ã1,2,0 x 2 + ã1,0,2 y 2 + ã1,1,1 xy + ã1,3,0 x 3 + ã1,2,1 x 2 y + ã1,1,2 xy 2 + ã1,0,3 y 3 ẏ = x + ã2,2,0 x 2 + ã2,0,2 y 2 + ã2,1,1 xy + ã2,30 x 3 + ã2,2,1 x 2 y + ã2,1,2 xy 2 + ã2,0,3 y 3 .
Observe that we can easily reconstruct the coefficient ãi,j,k from the ones in (3.1) by the change of coordinates (x, y) → (-x, y).

The classification of all the isochronous centers of the above system is a very hard task. By any recursive method from those quoted in [START_REF] Chavarriga | A survey of isochronous centers[END_REF], solving the isochronicity problem for system (3.1) is very difficult in the sense of solving multivariate polynomials. Here, the variables are the 14 parameters of the polynomial differential system (3.1). Hence it needs very important computation supports.

With a realistic point of view, several authors have chosen some particular cases of the above system for investigation like the homogeneous cubic perturbations of the linear center [START_REF] Pleshkan | A new method of investigating the isochronicity of a system of two differential equations[END_REF][START_REF] Chavarriga | A survey of isochronous centers[END_REF] and time reversible cubic systems [START_REF] Chen | Linearizability conditions of time-reversible cubic systems[END_REF][START_REF] Garcia | Contribution to the qualitative study of planar vector fields[END_REF].

In our case, we focus on an unknown 1-directional 1-parameter perturbation of the system (1.4) which is system (1.6). Therefore, we ramify our study to all possible cases.

In the sequel, every subsection will be concerned with a possible 1-parameter perturbation of system (1.4).

Recall that a i,j,k denotes the parameter of the monomial perturbation of the i th equation in system (1.4) of degree j in x and of degree k in y.

perturbation a 1,1,1

As a continuation of the result of [START_REF] Chouikha | Isochronous centers of Lienard type equations and applications[END_REF] on system (1.4), Chouikha, Romanovski and Chen investigated a 1-parameter perturbation of (1.4) which is (1.5). Theorem 3.1 (Chouikha et al. [START_REF] Chouikha | Chen Isochronicity of analytic systems via Urabe's criterion[END_REF]). System (1.5) has an isochronous center at the origin O if and only if

a 1,2,1 = -a1,1,1+a1,1,1a2,2,0-10a 2 2,2,0 +5a1,1,1a2,0,2-10a2,0,2a2,0,2-4a 2 2,0,2 +9a2,3,0+3a2,1,2 3
and it's parameters satisfy one of the following sets of conditions

1. 2a 2,2,0 + a 2,0,2 -a 1,1,1 = 0 a 2 2,0,2 -3a 2,0,2 a 1,1,1 + 2a 2 1,1,1 -6a 2,3,0 - 4a2,1,2 3 = 0 a 2,0,2 a 2,3,0 -3a 2,3,0 a 1,1,1 + a2,1,2a1,1,1 6 - a2,0,2a2,1,2 6 = 0 a 2 2,3,0 a 2 1,1,1 -3a 2 2,3,0 + a 2 1,1,1 a2,3,0a2,1,2 6 + a 2 2,3,0 a2,1,2 3 + 5a 2 2,1,2 a2,3,0 36 - a 3 2,1,2 5 = 0 a 2,1,2 a 1,1,1 a 2,0,2 + 6a 2,3,0 a 2 1,1,1 -a 2,1,2 a 2 1,1,1 -18a 2 2,3,0 -a 2,3,0 a 2,1,2 + 2a 2 2,1,2 3 = 0 2. a 2,1,2 = 0 and (a) a 2,3,0 = a 2,0,2 -1/4a 1,1,1 = a 2,2,0 = 0 (b) 4a 2,3,0 -3a 1,1,1 = a 2,2,0 + a 1,1,1 = a 2 1,1,1 -3a 2,3,0 = 0 (c) a 2,0,2 -2a 1,1,1 = a 2,3,0 -a 2 1,1,1 = a 2,2,0 + 2a 1,1,1 = 0 (d) a 2,0,2 -1/3a 1,1,1 = a 2,2,0 + 2/3a 1,1,1 = 9/2a 2,3,0 -a 2 1,1,1 = 0 3. a 2,3,0 = 0 and (a) a 2,2,0 + 1/2a 2,0,2 -1/2a 1,1,1 = a 2 2,0,2 -3a 2,0,2 a 1,1,1 + 2a 2 1,1,1 -a 2,1,2 = 0 (b) 2a 2,0,2 -a 1,1,1 = 2a 2,2,0 + a 1,1,1 = 0 (c) a 2,0,2 -a 1,1,1 = a 2,2,0 = 0 (d) a 2,0,2 = a 2 1,1,1 -9a 2,1,2 = a 2,2
,0 = 0 We contribute by classifying the isochronous centers of all the remaining 1-parameter perturbations of system (1.4). Eight systems are studied to do this. For these perturbations, first, we check if the center (at the origin O) conditions are satisfied and after we give necessary and sufficient isochronicity conditions depending only on the six real parameters.

Perturbation a 1,0,3

We are concerned by the following system

ẋ = y + a 1,2,1 x 2 y + a 1,0,3 y 3 ẏ = -x + a 2,2,0 x 2 + a 2,0,2 y 2 + a 2,3,0 x 3 + a 2,1,2 xy 2 (3.2)
Lemma 3.2. The investigation of isochronicity criteria of system (3.2) reduces to the investigation in the following three cases

1. a 1,0,3 = 0 2. a 1,0,3 = 1 3. a 1,0,3 = -1
Proof. For the case a 1,0,3 = 0, two cases are to be analyzed. First we assume that a 1,0,3 > 0. We use on (3.2) the change of coordinates :

(x, y) → a 1/2 1,0,3 (x, y) (3.3)
to obtain ẋ = y + a 1,2,1 a 1,0,3

x 2 y + y 3 ẏ = -x + a 2,2,0 a 1/2 1,0,3 x 2 + a 2,0,2 a 1/2 1,0,3 y 2 + a 2,3,0 a 1,0,3 x 2 + a 2,1,2 a 1,0,3 xy 2        . (3.4)
When the solutions of the isochronicity problem of system (3.4) are established, we can easily reconstruct those of the original system (3.2) by the transformation

(x, y) → (1/a 1/2 1,0,3 )(x, y). (3.5)
If a 1,0,3 < 0, then (3.2) can be written as

ẋ = y + a 1,2,1 x 2 y -ã1,0,3 y 3 ẏ = -x + a 2,2,0 x 2 + a 2,0,2 y 2 + a 2,3,0 x 3 + a 2,1,2 xy 2 with -a 1,0,3 = ã1,0,3 > 0. Applying the following change of coordinates (x, y) → ã1/2 1,0,3 (x, y) (3.6) yields ẋ = y + a 1,2,1 ã1,0,3 x 2 y -y 3 ẏ = -x + a 2,2,0 ã1/2 1,0,3 x 2 + a 2,0,2 ã1/2 1,0,3 y 2 + a 2,3,0 ã1,0,3 x 2 + a 2,1,2 ã1,0,3 xy 2        . (3.7)
The reconstruction of the solutions of (3.2) can be obtained from those of (3.7), by the change of coordinates (x, y) → (1/ã 1/2 1,0,3 )(x, y).

Remark 3.3. If one is concerned with quadratic perturbations of system (1.4) with the parameter a i,j,2-j we can consider the two cases namely, 1. a i,j,2-j = 0 2. a i,j,2-j = 1 Indeed, when a i,j,2-j = 0, the change of coordinates (x, y) → a i,j,2-j (x, y) reduces the problem to the case a i,j,2-j = 1.

Lastly, thanks to the transformation (x, y) → 1/a i,j,2-j (x, y), we can easily reconstruct the solutions of the problem when a i,j,2-j = 0. Theorem 3.4. System (3.2) has an isochronous center at O if and only if its parameters satisfy one of the following conditions :

1. a 1,0,3 = 0 (a) a 1,2,1 = a 2,1,2 , a 2,2,0 = a 2,0,2 = a 2,3,0 = 0 (b) a 1,2,1 = -3/2 a 2,3,0 , a 2,1,2 = -9/2 a 2,3,0 , a 2,2,0 = a 2,0,2 = 0 (c) a 1,2,1 = a 2,2,0 = -1/2, a 2,0,2 = 1, a 2,1,2 = -1, a 2,3,0 = 0 (d) a 1,2,1 = -1/7, a 2,2,0 = -1/2, a 2,0,2 = 1, a 2,3,0 = -1/14, a 2,1,2 = -3/7 2. a 1,0,3 = 1 (a) a 1,2,1 = -9/2, a 2,1,2 = -3/2, a 2,2,0 = a 2,0,2 = a 2,3,0 = 0 (b) a 2,3,0 = 1, a 1,2,1 = a 2,1,2 = -3, a 2,2,0 = a 2,0,2 = 0 (c) a 2,0,2 = -3/2, a 2,3,0 = 0, a 2,1,2 = a 1,2,1 = a 2,2,0 = 0 (d) a 2,0,2 = 3/2, a 2,3,0 = 0, a 2,1,2 = a 1,2,1 = a 2,2,0 = 0 (e) a 1,2,1 = -1, a 2,2,0 = a 2,0,2 = ± √ 2 2 , a 2,1,2 = -2, a 2,3,0 = 0, 3. a 1,0,3 = -1 (a) a 2,3,0 = -1, a 1,2,1 = a 2,1,2 = 3, a 2,2,0 = a 2,0,2 = 0 (b) a 1,2,1 = 9/2, a 2,1,2 = 3/2, a 2,3,0 = a 2,2,0 = a 2,0,2 = 0
In this proof, we do not present the algorithm generated polynomials which are too long.

Proof. We use the strategy given in lemma 3.2. We note also that we investigate only the real values of the parameters for which system (3.2) has an isochronous center at the origin. 1. Assume a 1,0,3 = 0 and then solve the isochronicity problem for system (3.2) under this assumption. We use the following change of coordinates (x, y) → (-x, y) to obtain system (1.4) studied in [START_REF] Chouikha | Isochronous centers of Lienard type equations and applications[END_REF]. The investigation following the two cases : (a) a 2,0,2 = 0 (b) a 2,0,2 = 1 covers, (with respect to a linear change of coordinates), all the values of the parameters for which the center at the origin of system (1.4), see Remark 3.3. In [START_REF] Chouikha | Isochronous centers of Lienard type equations and applications[END_REF], the author used Calgorithm which characterizes isochronicity by establishing associated Urabe function. 2. Consider the case a 1,0,3 = 1. Computations of normal forms of the initial system in polar form give (2.5)

ṙ = N j=1 α 2j+1 r 2j+1 + O(r 2N +3 ), θ = 1 + N j=1 β 2j+1 r 2j + O(r 2N +2 )
we obtain in the radial component α 2j+1 = 0 until order N = 6. So that the first six necessary conditions to have a center are satisfied. Analyzing isochronicity involves the angular component. Using FGb for computing the Gröbner basis of the obtained first six quantities in the angular component, we obtain a Gröbner basis of 27 polynomials denoted G 1 such that it's first element is -a 2,3,0 a 2,2,0 -a 2 2,1,2 + 9 a 2,3,0 . Then we analyze the isochronicity problem in the following three cases, which are given by the vanishing of one factor of the above expression.

(a) a 2,3,0 = 0, we substitute this condition into G 1 we compute again the associated Gröbner basis, we obtain a basis of 14 polynomials, when we solve it we obtain the following four real solutions to the problem :

(i) a 1,0,3 = 1, a 2,1,2 = -3/2, a 1,2,1 = -9/2, a 2,3,0 = a 2,2,0 = a 2,0,2 = 0 (ii) a 1,0,3 = 1, a 2,0,2 = 3/2, a 2,3,0 = a 1,2,1 = a 2,2,0 = a 2,1,2 = 0 (iii) a 1,0,3 = 1, a 2,0,2 = -3/2, a 2,3,0 = a 1,2,1 = a 2,2,0 = a 2,1,2 = 0 (iv) a 1,0,3 = 1, a 1,2,1 = -1, a 2,2,0 = a 2,0,2 = ± √ 2
2 , a 2,1,2 = -2 (b) For a 2,2,0 = 0, substituting this assumption in G 1 , and computing it's associated Gröbner basis which contains 7 polynomials, after solving it we obtain the solutions :

(i) a 1,0,3 = 1, a 2,0,2 = 3/2, a 2,2,0 = a 1,2,1 = a 2,3,0 = a 2,1,2 = 0 (ii) a 1,0,3 = 1, a 2,0,2 = -3/2, a 2,2,0 = a 1,2,1 = a 2,3,0 = a 2,1,2 = 0 (iii) a 1,0,3 = 1, a 2,1,2 = -3/2, a 1,2,1 = -9/2, a 2,2,0 = a 2,3,0 = a 2,0,2 = 0 (iv) a 1,0,3 = a 2,3,0 = 1, a 2,1,2 = a 1,2,1 = -3, a 2,2,0 = a 2,0,2 = 0 (c) Similarly for a 2,3,0 = (1/9)a 2 2,1,2 , we obtain the solutions (i) a 1,0,3 = 1, a 2,0,2 = -3/2, a 2,2,0 = a 1,2,1 = a 2,3,0 = a 2,1,2 = 0 (ii) a 1,0,3 = 1, a 2,0,2 = 3/2, a 2,2,0 = a 1,2,1 = a 2,3,0 = a 2,1,2 = 0 (iii) a 1,0,3 = a 2,3,0 = 1, a 2,1,2 = a 1,2,1 = -3, a 2,2,0 = a 2,0,2 = 0
It's easy to see that several solutions are repeated above. For example cases (2(a)ii ≡ 2(b)i) and (2(a)iii ≡ 2(b)ii). We claim that there are only 5 solutions to the problem when a 1,0,3 = 1 which are given in the theorem.

Analysis of the theorem cases with a 1,0,3 = 1 • 2a-In this case system (3.2) reduces to

ẋ = y -9/2yx 2 + y 3 ẏ = -x -3/2xy 2
which is a cubic homogeneous perturbation of linear center with isochronous center at the origin. Indeed, we use the change of coordinates (x, y) → ( y √ 2 , x √ 2 ) we obtain system S * 3 given in [START_REF] Chavarriga | A survey of isochronous centers[END_REF][START_REF] Pleshkan | A new method of investigating the isochronicity of a system of two differential equations[END_REF]. A first integral, a linearizing change of coordinate and a transversal commuting system are established for homogeneous perturbations (see [START_REF] Mardesić | Linearization of isochronous Centers[END_REF][START_REF] Chavarriga | A survey of isochronous centers[END_REF]).

• 2b-System (3.2) reduces to ẋ = y -3 x 2 y + y 3 ẏ = -x + x 3 -3 xy 2
which is an homogeneous perturbation of linear center, by the change of coordinates (x, y) → (y, x) reduces to system S * 1 of [START_REF] Pleshkan | A new method of investigating the isochronicity of a system of two differential equations[END_REF][START_REF] Mardesić | Linearization of isochronous Centers[END_REF][START_REF] Chavarriga | A survey of isochronous centers[END_REF]. • 2c-and 2d-For these two cases system (3.2) reduces to

ẋ = y + y 3 ẏ = -x ± 3/2 y 2
We see that by the change of coordinate (x, y) → (y, x), we have a Liénard systems x + f (x)x + g(x) = 0 satisfying

g(x) = g (0)x + 1 x 3 ( x 0 sf (s)ds) 2 (3.8)
then the origin is an isochronous center. See [START_REF] Chouikha | Monotonicity of the period function for some planar differential systems. Part II: Liénard and related systems[END_REF][START_REF] Christopher | On the classification of Lienard systems with amplitude-independent periods[END_REF][START_REF] Algaba | Isochronicity via normal form[END_REF] for more details about characterization of isochronicity for Liénard equation. • 2e-In this case system (3.2) is a time-reversible system with an isochronous center at O. Indeed, in polar coordinates it reduces to

ṙ = -1/2 sin (θ) r 2 √ 2 + 1/2 r 3 sin (2 θ) θ = 1 + (-1/2 cos (2 θ) + 1/2) r 2 -1/2 r cos (θ) √ 2
which belongs to the family ii) (with

R 1 = r 1 = - √ 2 2 if a 2,2,0 = a 2,0,2 = √ 2
2 ) and (R

1 = r 1 = √ 2 2 if a 2,2,0 = a 2,0,2 = - √ 2
2 ) of the theorem 8.11 in Garcia thesis, see also system CR 4 of [START_REF] Chavarriga | A survey of isochronous centers[END_REF].

3. a 1,0,3 = -1. When executing the normal form Maple code, there is no change from the case a 1,0,3 = 1 : the coefficients of radial component of system (2.5) are such that α 2j+1 = 0 until order N = 6. The first six necessary conditions to have a center are satisfied. On a similar way as the case a 1,0,3 = 1, for analyzing isochronicity we are concerned by the angular component. We compute the Gröbner basis ,denoted G -1 , of the obtained first six quantities in the angular component. We obtain an ideal of 27 polynomials such that its first element is a 2,2,0 a 2,3,0 a 2 2,1,2 + 9a 2,3,0 . Then we analyze the isochronicity problem in the following three cases, which are the vanishing of each of the factors of the above expression.

(a) For a 2,3,0 = 0, we substitute this assumption in G -1 . We compute again the Gröbner basis associated to this case. We obtain a basis of 14 polynomials. when we solve it we obtain the unique real solution to the problem : (i) a 1,0,3 = -1, a 1,2,1 = 9/2, a 2,1,2 = 3/2, a 2,3,0 = a 2,2,0 = a 2,0,2 = 0 (b) For a 2,2,0 = 0 we do the same as for the last case and obtain the two real solutions

(i) a 1,0,3 = a 2,3,0 = -1, a 1,2,1 = a 2,1,2 = 3, a 2,2,0 = a 2,0,2 = 0 (ii) a 1,0,3 = -1, a 1,2,1 = 9/2, a 2,1,2 = 3/2, a 2,3,0 = a 2,2,0 = a 2,0,2 = 0 (c) a 2,3,0 = -(1/9)a 2
2,1,2 in the same way as for the first and second cases we obtain (i) a 1,0,3 = a 2,3,0 = -1, a 1,2,1 = a 2,1,2 = 3, a 2,2,0 = a 2,0,2 = 0 We conclude that in the case a 1,0,3 = -1, we have only two solutions to the isochronicity problem.

Analysis of the theorem cases with a 1,0,3 = -1 These two solutions are cubic homogeneous perturbations of the linear center, which can be found in [START_REF] Chavarriga | A survey of isochronous centers[END_REF].

• 3a-in this case, system (3.2) can be written

ẋ = y + 3 x 2 y -y 3 ẏ = -x -x 3 + 3 xy 2
by the change of coordinates (x, y) → (-x, -y), it reduces to system S * 1 of [START_REF] Pleshkan | A new method of investigating the isochronicity of a system of two differential equations[END_REF][START_REF] Mardesić | Linearization of isochronous Centers[END_REF][START_REF] Chavarriga | A survey of isochronous centers[END_REF], which have an isochronous center at the origin. • 3b-system (3.2) can be written

ẋ = y + 9/2yx 2 -y 3 ẏ = -x + 3/2xy 2
we use the change of coordinates (x, y) → ( y √ 2 , x √ 2 ) we obtain system S * 3 with isochronous center at the origin O given in [START_REF] Chavarriga | A survey of isochronous centers[END_REF][START_REF] Pleshkan | A new method of investigating the isochronicity of a system of two differential equations[END_REF]. That ends the proof.

Perturbation a 1,3,0

Consider the system

ẋ = y + a 1,2,1 x 2 y + a 1,3,0 x 3 ẏ = -x + a 2,2,0 x 2 + a 2,0,2 y 2 + a 2,3,0 x 3 + a 2,1,2 xy 2 (3.9)
Theorem 3.5. System (3.9) with a 1,3,0 = 0 has no center at the origin. Moreover, system (3.9) has an isochronous center at the origin O if and only if it reduces to system (1.4) and its parameters satisfy one of isochronicity cases from those of Theorem (1.1).

Proof. Analogously to lemma 3.2 we have to analyse a 1,3,0 = ±1. Executing the Maple code, which gives the normal form of (3.9) in it's polar form (2.5)

ṙ = N j=1 α 2j+1 r 2j+1 + O(r 2N +3 ), θ = 1 + N j=1 β 2j+1 r 2j + O(r 2N +2 )
we obtain in the radial component such that α 3 = ± 3 8 , then in this case, the singular point can not be a center.

3.4. Perturbation a 2,0,3 This perturbation represents system (1.4) perturbed by the additional monomial with the parameter a 2,0,3 ẋ = y + a 1,2,1 x 2 y ẏ = -x + a 2,2,0 x 2 + a 2,0,2 y 2 + a 2,3,0 x 3 + a 2,1,2 xy 2 + a 2,0,3 y

Theorem 3.6. System (3.10) with a 2,0,3 = 0 has no center at the origin. Moreover, system (3.10) has an isochronous center at O if and only if it reduces to system (1.4) and its parameters satisfy one case of isochronicity conditions given in Theorem (1.1).

Proof. Analogously to lemma 3.2. Consider a 2,0,3 = ±1. Executing the Maple code, which gives the normal form of (3.10) in it's polar form (2.5)

ṙ = N j=1 α 2j+1 r 2j+1 + O(r 2N +3 ), θ = 1 + N j=1 β 2j+1 r 2j + O(r 2N +2 )
we obtain in the radial component such that α 3 = ± 3 8 , then in this case, the singular point cant be a center.

Perturbation a 1,1,2

This case represents system (1.4) perturbed by the monomial with the parameter a 1,1,2 Proof. when a 1,1,2 = 0 we obtain in the radial component α 3 = ± 1 8 , then in this case, the singular point at the origin cant be a center.

ẋ = y + a 1,2,1 x 2 y + a 1,1,2 xy 2 ẏ = -x + a 2,2,0 x 2 + a 2,0,2 y 2 + a 2,3,0 x 3 + a 2,
3.6. Perturbation a 2,2,1 This case represents system (1.4) perturbed by the monomial with the parameter a 2,2,1 ẋ = y + a 1,2,1 x 2 y ẏ = -x + a 2,2,0 x 2 + a 2,0,2 y 2 + a 2,3,0 x 3 + a 2,1,2 xy 2 + a 2,2,1 x 2 y (3.12)

Theorem 3.8. System (3.12) with a 2,2,1 = 0 has no center at the origin. Moreover, system (3.12) has an isochronous center at O if and only if it reduces to one case of isochronicity from those of system (1.4).

Proof. By the same reason from the one of the last case, we substitute a 2,2,1 = ±1 in the system, then we obtain in the radial component α 3 = ± 1 8 , in this case, the singular point at the origin can not be a center.

3.7.

Perturbation a 1,0,2 This perturbation represents system (1.4) with an additional monomial a 1,0,2 y 2 in the first equation . ẋ = y + a 1,2,1 x 2 y + a 1,0,2 y 2 ẏ = -x + a 2,2,0 x 2 + a 2,0,2 y 2 + a 2,3,0 x 3 + a 2,1,2 xy 2 (3.13) Theorem 3.9. System (3.13) with a 1,0,2 = 0 has no isochronous center at the origin. Moreover, system (3.13) has an isochronous center at O if and only if a 1,0,2 = 0 and it reduces (modulo a linear change of coordinates) to system (1.4) such as its parameters satisfy one of the four cases given in Theorem 1.1.

Proof. Since we have a quadratic perturbation of system (1.4), thanks to Remark 1 we study the cases a 1,0,2 ∈ {0, 1}. If a 1,0,2 = 0, system (3.13) admit an isochronous center at the origin if and only if it reduces to (1.4) and its parameters satisfy one the isochronicity conditions given by Theorem 1.1. We assume a 1,0,2 = 1, and we compute first the radial component of the normal form in polar coordinates. The first radial component α 3 = -a 2,0,2 /4, then we substitute the assumption a 2,0,2 = 0 in the remaining five α 2j+1 and we compute the associated Gröbner base, we find α 5 = a 2,2,0 (a 2,1,2 + a 1,2,1 ). We continue the analysis in the three cases : 1. a 2,2,0 = 0 2. (a 2,1,2 + a 1,2,1 ) = 0 Unfortunately, we computed in each case the Gröbner base and there are no common roots between the multivariate polynomials β 2j+1 of the angular component.

ẋ = y + a 1,2,1 x 2 y + a 1,2,0 x 2 ẏ = -x + a 2,2,0 x 2 + a 2,0,2 y 2 + a 2,3,0 x 3 + a 2,1,2 xy 2 (3.14)
Theorem 3.10. System (3.14) with a 1,2,0 = 0 has an isochronous center at O if and only if ,modulo a linear change of coordinates, its parameters satisfy a 2,3,0 = -4/9, a 2,1,2 = 0, a 1,2,1 = 0, a 2,2,0 = 0, a 2,0,2 = 0, a 1,2,0 = 1

Proof. Consider the case a 1,2,0 = 1. We compute first, under this assumption, the radial component of the normal form of system (3.14). We obtain α 3 = a 2,2,0 /4. Then the first necessary condition to have a center at the origin is the vanishing of a 2,2,0 . We substitute this additional assumption in the remaining coefficients of the radial component (α 5 . . . α 13 ). A common factor appears which is a 2,0,2 .

Hence we obtain two cases to analyse center conditions a 2,0,2 = 0 and a 2,0,2 = 0. For the case a 2,0,2 = 0, we divide all the expressions of the coefficients of the radial component by a 2,0,2 . We compute the associated Gröbner basis which is generated by 8 polynomials and gives 3 cases for each one the first six necessary conditions for the center are satisfied. Namely the following

{a 2,1,2 = 0, a 1,2,1 = 0, a 2,2,0 = 0, a 2,0,2 = 0, a 1,2,0 = 1, a 2,3,0 = -3/4} {a 2,2,0 = 0, a 1,2,0 = 1, a 2,3,0 = 0, a 2,0,2 = -1, a 2,1,2 = -a 1,2,1 } {a 2,2,0 = 0, a 1,2,0 = 1, a 2,3,0 = 0, a 2,1,2 = -a 1,2,1 , a 2,0,2 = 1}
The first solution is rejected, because we have assumed that a 2,0,2 = 0.

For the second and the third solution of center condition investigation, we substitute each of those into the angular component coefficients expressions. We compute the Gröbner bases of the obtained multivariate polynomial systems. Unfortunately in the two cases it gives Gröbner basis ≡ [START_REF] Algaba | Isochronicity via normal form[END_REF] which means that there are not common roots.

We return to the remaining case a 1,2,0 = 1, a 2,2,0 = a 2,0,2 = 0 which ensures the first six necessary conditions of the singular point at the origin to be a center. Substituting this assumption in the angular component coefficients and computing its associated Gröbner basis which is generated by three polynomials. This gives the unique solution to the problem of isochronicity

a 2,3,0 = -4/9, a 1,2,0 = 1, a 2,1,2 = a 1,2,1 = a 2,2,0 = a 2,0,2 = 0 Then system (3.14) reduces to ẋ = y + x 2 ẏ = -x -4/9 x 3 Which is a Liénard isochronous system with f (x) = -2 x, g(x) = x + 4/9 x 3 satisfying g(x) = g (0)x + 1 x 3 ( x 0 sf (s)ds) 2 3.9. Perturbation a 2,1,1 ẋ = y + a 1,2,1 x 2 y ẏ = -x + a 2,2,0 x 2 + a 2,0,2 y 2 + a 2,1,1 xy + a 2,3,0 x 3 + a 2,
1. a 2,1,1 = 1, a 2,3,0 = -1/9, a 2,1,2 = a 1,2,1 = a 2,2,0 = a 2,0,2 = 0 2. a 2,1,1 = 1, a 2,1,2 = -2/9, a 1,2,1 = 1/9, a 2,2,0 = a 2,0,2 = a 2,3,0 = 0 Proof. Consider the a 2,1,1 = 1
We compute first, under this assumption, the radial component of the normal form of system (3.15). We obtain α 3 = (a 2,0,2 + a 2,2,0 )/8, then the first necessary condition to have a center at the origin is the vanishing of α 3 .

We substitute this additional assumption a 2,0,2 = -a 2,2,0 in the following coefficient of the radial component α 5 = -1/48 a 2,0,2 (a 1,2,1 -a 2,1,2 + a 2,3,0 ), then it appears two cases to analyze: {a 2,0,2 = a 2,2,0 = 0} and {a 2,0,2 = -a 2,2,0 , a 1,2,1 -a 2,1,2 + a 2,3,0 = 0} 1. a 2,0,2 = a 2,2,0 = 0 We substitute this additional assumption in the remaining coefficients of the radial component α 7 , . . . , α 13 which gives α 3 = α 5 . . . = α 13 = 0. Hence, the first six center necessary conditions are satisfied.

Substituting the assumptions into the angular component coefficients expressions, computing associated Gröbner basis gives the two real solutions. The first one is {a 2,1,1 = 1, a 2,3,0 = -1/9, a 2,1,2 = a 2,2,0 = a 2,0,2 = a 1,2,1 = 0} under which system (3.15) The second one is Which belongs to the Liénard Type equation (1.2) with f (x) = -3 (2 x -3) -1 and g(x) = 1/9 x (2 x -3) (x -3). The isochronicity of this last system is proved since it belongs to the case 9 of the Theorem 3 of Chouikha et.al in [START_REF] Chouikha | Chen Isochronicity of analytic systems via Urabe's criterion[END_REF]. 2. a 2,0,2 = -a 2,2,0 and a 1,2,1 -a 2,1,2 + a 2,3,0 = 0 Unfortunately in this case, after computing Gröbner basis, no real solutions are found.

Theorem 3.12. System (1.4) has an amplitude independent frequency synchronizer at O if and only if its parameters satisfy one of the cases of Theorem 3-Theorem 11.

To summarize, for the eight monomial perturbations studied in this paper we have identified all possible amplitude independent frequency synchronizer. Moreover, we claim that all isochronous cases are known in a fragmented literature but our study insures that for the studied family there are no other (necessary conditions). Each of them was found in a classification of a specific family of planar differential systems which are different from the context of the ones studied in this paper (synchronization). For isochronous centers of Liénard systems the reader can see for instance [START_REF] Christopher | On the classification of Lienard systems with amplitude-independent periods[END_REF][START_REF] Chavarriga | A survey of isochronous centers[END_REF]. The papers [START_REF] Chouikha | Isochronous centers of Lienard type equations and applications[END_REF][START_REF] Chouikha | Chen Isochronicity of analytic systems via Urabe's criterion[END_REF] are concerned with the planar differential Liénard Type equations. For cubic time reversible systems see [START_REF] Chavarriga | A survey of isochronous centers[END_REF][START_REF] Garcia | Contribution to the qualitative study of planar vector fields[END_REF][START_REF] Chen | Linearizability conditions of time-reversible cubic systems[END_REF] and for cubic homogeneous perturbations of linear center see [START_REF] Chavarriga | A survey of isochronous centers[END_REF][START_REF] Garcia | Contribution to the qualitative study of planar vector fields[END_REF][START_REF] Mardesić | Linearization of isochronous Centers[END_REF].

3. 8 .

 8 Perturbation a 1,2,0 Consider the system

  reduces to ẋ = y ẏ = -x + xy -1/9 x 3 we have an isochronous Liénard systems with f (x) = -x and g(x) = x + 1/9 x 3 which satisfy g(x) = g (0)x + 1 x 3 ( x 0 sf (s)ds) 2

{a 2 ,

 2 2,0 = 0, a 2,0,2 = 0, a 2,1,1 = 1, a 2,3,0 = 0, a 2,1,2 = -2/9,a 1,2,1 = 1/9} under which system (3.15) reduces to ẋ = y + 1/9x 2 y ẏ = -x + xy -2/9 xy 2 By the change of coordinates (x, y) → (y, x) we obtain ẋ = -y + xy -2/9 x 2 y ẏ = x + 1/9 xy 2

  System (3.11) with a 1,1,2 = 0 has no center at the origin. Moreover, system (3.11) has an isochronous center at O if and only if it reduces to one case of isochronicity from those of system (1.4).

	1,2 xy 2	(3.11)
	Theorem 3.7.

Journal of Computational and Nonlinear Dynamics, (ASME), April 2012, Volume 7, Issue 2, 021009, (8 pp).

Acknowledgment

Financial support by the Institut Polytechnique des Sciences Avancées is gratefully acknowledged. I warmly thank Silviu-Iulian Niculescu and Hugues Mounier who indroduced me to Engineering Sciences during my Post-doctoral stay at L2S, CNRS-Supélec-Université Paris Sud. I am grateful to A.Raouf Chouikha (Université Paris 13, France) and Jean-Marie Strelcyn (Université de Rouen, France) and Andrzej Maciejewski (University of Zielona Gòra, Poland) for many important hints and fruitful discussions. I am also indebted to Antonio Loria for constructive discussions about the synchronization problem during an advanced course in this topic organized by the EECI-HYCON2 Graduate School on Control held in january 2011 at L2S. Last but not least, I thank the anonymous referees for their suggestions.