Possibilistic ASP Base Revision by Certain Input

1 Introduction

The paper deals with belief revision within the context of incomplete and uncertain information. Our main motivation comes from reasoning with data from the Web which are commonly represented by means of ontologies and description logics (DL). Such data are often incomplete, imprecise and, supplied by several sources, have different confidence levels. A non-monotonic logic framework able to handle uncertainty is then suitable to address knowledge change in this context.

Belief revision consists in incorporating new information, changing as little as possible an agent's initial beliefs while preserving consistency. After the seminal work of AGM [Alchourr´on and Makinson, 1985], belief revision has been extensively studied within a classical setting according to model-based [Katsuno and Mendelzon, 1991] and formulabased (or base) [Hansson, 1999] standpoints.

Little research investigated belief revision when the underlying logic is non-monotonic. Most approaches were proposed for Answer Set Programming (ASP) [Gelfond and Lifschitz, 1988; Schaub, 2008] which is an efficient unified formalism for both knowledge representation and reasoning in Artificial Intelligence. The two main approaches are modelbased revision for logic programs [Delgrande et al., 2013; Slota and Leite, 2014], stemming from SE-models [Turner, 2003], and rule-based revision from two standpoints: "remainder sets" [Kr¨umpelmann and Kern-Isberner, 2012] and

"removed sets" [Hu´e et al., 2013] approaches. Rule-based revision relies on the removal of some rules in order to restore consistency, while new strategies stemming from the addition and/or removal of some rules have been proposed [Zhuang et al., 2016; Garcia et al., 2017].

In order to deal with uncertainty in a non-monotonic formalism, ASP was extended by integrating a theory that copes with uncertainty. Probabilities are the widely used one and their applications to ASP has been proposed [Baral et al., 2009; Wang and Lee, 2015; de Morais and Finger, 2013]. Nevertheless, when dealing with knowledge where uncertainty is expressed by subjective levels, a qualitative setting is more suitable and we choose to use possibilities where the values represent a level in a scale [Dubois and Prade, 2001].

ASP was extended to possibilistic ASP [Nicolas et al., 2006; Bauters et al., 2015] with a possibilistic answer set semantics stemming from possibility theory [Dubois and Prade, 1998; 1988]. The initial work [Nicolas et al., 2005] is directly inspired from the classical setting and the answer sets of a possibilistic ASP program match with the (classical) answer sets of the corresponding program without weights. On the other hand, in [Bauters et al., 2010], the strength of the negative body of a rule is taken into account but it requires an additional guess to determine the weights of the answers, thus the resulting answer sets do not match with the classical ones. In the present work, we use the framework proposed in [Nicolas et al., 2006].

Within the context of reasoning with Web applications, there is an increasing interest in bridging ontologies languages and logic programming [Eiter et al., 2008; Motik and Rosati, 2010; Lopes et al., 2017]. In particular, ASP has been extended with existential variables in order to represent DL knowledge bases (KB) [Baget et al., 2018]. Moreover, in a dynamic setting, ASP has been used to repair DL ontologies [Baget et al., 2016]. Besides, uncertain pieces of information can be represented in possibilistic DL-Lite [Benferhat and Bouraoui, 2017]. A step further is to study the dynamics of possibilistic ASP in order to provide a computational framework for the dynamics of possibilistic DL KB. The contribution of this paper is a study of belief base revision within the framework of possibilistic ASP when the input is certain. The certainty of input corresponds to one of the revision principles which specifies that new information has to be accepted.

The paper is organized as follows. After a refresher on possibilistic ASP, two approaches of possibilistic ASP base revision are proposed. The first one, called "standard possibilistic ASP base revision" stems from the strategy of keeping the most certain possibilistic rules beyond the inconsistency degree. However, if the goal is to change as little as possible the original beliefs, it suffers from the "drowning problem" (unnecessary removal of rules not involved in inconsistency). In order to overcome this problem we introduce another approach, called "RSR possibilistic ASP base revision" which is based on the strategy of removing a minimum number of the least certain possibilistic rules, keeping the possibilistic rules not involved in inconsistency. A semantic characterization of these revision operators in terms of possibilistic distribution is then provided. Logical properties of the proposed operators are presented as well as a computational complexity study.

2 Background

2.1 Possibilistic Answer Set Programming

In this subsection, we recall the definitions about possibilistic answer set programming that can be found in [Nicolas et al., 2006].

Language of possibilistic ASP We consider given a finite set of atoms X and a finite, totally ordered set of necessity values N ⊆]0, 1]. Let us first recall, that, as in possibilistic logic, these values are evaluated by a necessity measure and are not probabilities. Thus, they are not an absolute evaluation (like it is done in probability theory) but induce a certainty (or confidence) scale allowing to order beliefs. When the level of the belief is 1, it is considered as certain. Let us note that a piece of information with a necessity degree equal to 0 is not taken into account because it means that this piece is impossible.

A possibilistic atom is a pair p = (x, α) ∈ X ×N . The set of atom sets is denoted by 2X and the set of possibilistic atom sets, in which every atom occurs at most once, is denoted by A. We denote by p∗ = x the classical projection of p and by n(p) = α its necessity degree. Projection is extended to possibilistic atom sets in the usual way. A possibilistic ASP program is a finite set of rules r such that:

where n ≥ 0,m ≥ 0, c, a1, . . . , an, b1, . . . , bm ∈ X and α ∈ N. We denote by r∗ = (c ← a1, . . . , an, not b1, . . . , not bm) the classical projection of the rule r and n(r) = α its necessity degree representing the certainty level of the information described by the rule. The set of possibilistic ASP programs, in which every (classical) rule occurs at most once, is denoted by P. The weight of P ∈ P is defined by w(P) = max{α | (r, α) ∈ P}.

A rule of the form r = (c ← a1, . . . , an, α) is called a possibilistic definite rule. When a program contains only possibilistic definite rules, it is called a possibilistic definite logic program. The set of possibilistic definite logic programs is denoted by Pd.

We recall some operations over possibilistic ASP programs useful in the following. Let P,Q ∈ P

P ⊔ Q = {(r, α) | (r, α) ∈ P, r ̸∈ Q∗ } ∪ {(r, β) | r ̸∈ P ∗ , (r, β) ∈ Q, } ∪ {(r,max{α, β}) | (r, α) ∈ P, (r, β) ∈ Q}. P \p Q = {(r, α) | (r, α) ∈ P, (r ̸∈ Q∗ ) or (∃β | (r, β) ∈ Q and β < α)}

For a classical (without weight) rule r, we use the following notations: body+(r) = {a1, . . . , an} is the positive body, body-(r) = {b1, . . . , bm} is the negative body, head(r) = c is the head and r+ = head(r) ← body+(r) is the positive projection of the rule. These functions, defined for rules, are extended to rule sets as usual.

Possibilistic answer sets As in the classical case without necessity value, the definition of the answer sets is given by using the reduct of a program.

Definition 1. Let P ∈ P and A ∈ 2X . The possibilistic reduct of P w.r.t. A is the possibilistic definite logic program P A = {(r∗+, n(r)) | r ∈ P, body-(r∗ ) ∩ A = ∅}.

Definition 2. Let r = (c ← a1, . . . , an, α) be a definite possibilistic rule (body-(r∗ ) = ∅) and A ∈ A, r is β-applicable in A if {(a1, α1), . . . , (an, αn)} ⊆ A and β = min {α, α1, . . . , αn}.

For a given P ∈ Pd and A ∈ 2X , App(P, A) = {r ∈ P ∗ | body+(r) ⊆ A}.

Definition 3. Let P ∈ Pd and A ∈ A. The immediate possibilistic consequence operator ΠTP is a function from A to A such that:

max r∈P {ν | r is ν-applicable in A and x = head(r∗ )}

then the iterated operator ΠT k P is defined by ΠT 0 P = ∅ and ΠT n+1 P = ΠTP (ΠT n P ), ∀n ≥ 0.

Proposition 1 ([Nicolas et al., 2006]). Let P ∈ Pd, then ΠTP has a least fix-point ⊔n≥0ΠT n P that we called the set of possibilistic consequences of P and we denote it by ΠCn(P ).

By this way, the definition of a possibilistic answer set is natural.

Definition 4. Let P ∈ P and S ∈ A. S is a possibilistic answer set of P if S = ΠCn(P (S∗ ) ).

The set of all possibilistic answer sets of P is denoted by ΠAS(P). Note that there is a one to one correspondence between the possibilistic answer sets of a possibilistic program P and the answer sets of its projection P ∗ .

Possibility distribution From a semantic point of view, a possibility distribution is defined over interpretations w.r.t. a possibilistic logic program. The possibility degree of each interpretation is induced by the necessity degrees associated to the falsified rules. This possibility degree reflects the ability of the interpretation to be an answer set of the program.

Let P ∈ P and A ∈ 2X , then Fal(P,A) = {r ∈ P | body+(r∗ ) ⊆ A, body-(r∗ ) ∩ A = ∅, head(r∗ ) ̸∈ A} denotes the set of the rules of a possibilistic program P that are falsified w.r.t. an atom set A.

A set of classical rules R is grounded if there exists an enumeration 〈r1 . . . rn〉 of the rules of R such that ∀i ∈ [1..n], body+(ri) ⊆ head{rj | j < i}.

Definition 5. Let P ∈ Pd, the least possibility distribution πP : 2X → [0, 1] is defined by: for each A ∈ 2X

• if A ̸⊆ head(App(P,A)) then πP (A) = 0,
• if App(P, A) is not grounded then πP (A) = 0,
• if A is an answer set of P ∗ then πP (A) = 1,
• otherwise πP (A) = 1-w(Fal(P,A)).

The distribution defined on definite programs can be used to define a distribution on ASP programs:

Definition 6. Let P ∈ P, the possibility distribution ˜πP : 2X → [0, 1] is defined by: for each A ∈ 2X ˜πP (A) = πP A(A).

The following proposition shows that the interpretations with a value of 1 match with the answer sets of the possibilistic program without weights.

Proposition 2 ([Nicolas et al., 2006]). Let P ∈ P and A ∈ 2X . ˜πP (A) = 1 if and only if A ∈ ΠAS(P)∗ .

Consistency in possibilistic ASP We say that P ∈ P is consistent if ΠAS(P) ̸= ∅ or, equivalently, if ∃A ∈ 2X such that ˜πP (A) = 1. Otherwise P is said inconsistent.

We can also consider monotonic consistency. Let P ∈ P and A ∈ 2X , A is a (classical) model of P if Fal(P, A) = ∅. The set of models of P is denoted by Mod(P). P ∈ P is m-consistent if Mod(P) ̸= ∅. Otherwise P is said minconsistent.

2.2 Notations

We review some notations useful in subsequent sections. A preorder on a set A is a reflexive and transitive binary relation. A total preorder, denoted by ≤, is a preorder such that ∀x, y ∈ A either x ≤ y or y ≤ x holds. Equivalence is defined by x ≃ y if x ≤ y and y ≤ x. The corresponding strict total preorder, denoted by <, is the relation defined by x < y if x ≤ y holds but x ≃ y does not hold. Let M be a subset of A, the set of minimal elements of M with respect to ≤, denoted by Min(M, ≤), is defined as: Min(M, ≤) = {x ∈ M | ∄y ∈M, y < x}.

Let X and Y be two sets, |X| (resp. |Y |) denotes the cardinality of X (resp. of Y ) and X ≤Card Y if |X| ≤ |Y |.

Let A be a finite set, a selection function denoted by f is a function from 2A \ ∅ to A which for any non empty set X ∈ 2A returns an element f(X) such that f(X) ∈ X.

3 Possibilistic ASP Base Revision

The belief revision principles state that new information has to be accepted, the revised agent's beliefs have to be consistent and the initial agent's beliefs have to be changed as little as possible. This section studies belief revision when agent's beliefs and new information are represented by possibilistic ASP programs. In the following, according to the revision principles, we assume that the rules of the program to be revised P are not certain, i.e. w(P) < 1. The input is a possibilistic ASP program Q which is assumed to be certain, i.e. ∀r ∈ Q, n(r) = 1. Moreover, we suppose that Q is m-consistent otherwise revising by Q is impossible.

We present two different rule-based revision strategies. The first one, focuses on keeping the most certain possibilistic rules of P beyond the consistency degree, while the second one focuses on removing a minimum number of the least certain rules of P, keeping the rules of P not involved in inconsistency.

3.1 Standard Possibilistic ASP Base Revision

The revision presented here follows the approach of [Nicolas et al., 2006] to restore consistency of a possibilistic normal logic program by deleting less certain rules. In this view, if a rule (r, α) must be removed in order to restore consistency, then all the rules with a degree less or equal to α have to be removed too. Indeed, questioning a belief is questioning all beliefs with lower necessity.

We first recall some additional notions from [Nicolas et al., 2006]. Let P ∈ P the α-cut of P, denoted by P>α, is such that P>α = {(ri, αi) ∈ P | αi > α}. The inconsistency degree of P, denoted by Inc(P), is such that Inc(P) = min{α | α ∈ N ∪ {0}, P>α is consistent}. The inconsistency degree of P defines the minimum level of certainty for which a cut of P is consistent. But, it is not necessarily the greatest (in number of rules) consistent subprogram of P .

The standard possibilistic ASP revision operator, denoted by ⊛Π, is a function from P × P to P defined as follows.

Definition 7. Let P, Q ∈ P with w(P ) < 1, ∀r ∈ Q, n(r) = 1 and Q is m-consistent.

The following example illustrates the behavior of the ⊛Π revision operator.

Example 1. Let P = {r1 : (b ← not c, 0.9), r2 : (d ← , 0.8), r3 : (c ← not a, 0.8), r4 : (e ←, 0.7)} and Q = {r0 : (a ←not b, 1)}. The inconsistency of P ⊔Q comes from the rules {r0, r1, r3}. We have ΠAS(P ⊔Q) = ∅ and Inc(P⊔Q) = 0.8, the revised possibilistic logic program is P ⊛ΠQ = {r0, r1}. Note that the rules r2 and r4 which do not contribute to the inconsistency of P ⊔Q do not appear in the revised logic program because they are less certain than the "guilty" rule r3.

Note that if P ⊔Q is consistent then Inc(P ⊔Q) = 0 therefore P ⊛Π Q = P ⊔Q. If Inc(P ⊔Q) = 1 then P ⊛Π Q = ∅ and ΠAS(P ⊛ΠQ) = {∅}. That means that Q is inconsistent and that nothing can be done (with the present strategy) to restore the consistency as illustrated in the following example.

When dealing with possibility theory where necessity degrees represent levels of certainty, it is natural to remove all the rules that are less certain that the rules responsible for inconsistency. However, if the weights represent priorities and if the goal is to remove the smallest number of rules w.r.t. priorities, it is necessary to define a less drastic revision strategy.

3.2 RSR Possibilistic ASP Base Revision

We extend Removed Sets Revision (RSR) [Hu´e et al., 2013] to possibilistic ASP. This strategy focuses on the minimal number of possibilistic rules of least degree of necessity to remove in order to restore consistency. Here, only the rules involved in inconsistency are removed. We first introduce the notion of possibilistic potential removed set.

Definition 8 (possibilistic potential removed set). Let P, Q ∈ P, a possibilistic potential removed set X is such that: (i) X ⊆ P. (ii) (P \ X) ⊔ Q is consistent. (iii) For each X′ ⊂X, (P \X′ ) ⊔Q is inconsistent.

PR(P,Q) denotes the set of possibilistic potential removed sets for P and Q. According to the definition, if P ⊔Q is consistent then PR(P, Q) = {∅}. Since only rules from P can be removed in order to restore consistency of P ⊔ Q, it may be possible that the set of potential removed sets for an inconsistent program Q is empty which is the case considering P and Q from Example 2.

In order to keep the rules with the highest degrees of necessity we define a total pre-order on possibilistic potential removed sets, denoted by ≤w, based on the weight of a set of possibilistic rules: for all X, Y possibilistic potential removed sets, X ≤w Y if and only if w(X) ≤ w(Y ). Moreover, we use the cardinality minimality criterion on possibilistic potential removed sets of minimal weight.

Definition 9 (possibilistic removed set). Let P,Q ∈ P, a possibilistic removed set X is such that: (i) X ∈ PR(P, Q). (ii) ∄Y ∈ PR(P,Q) such that Y <w X. (iii) ∄Y ∈ PR(P,Q) such that Y ≃w X and Y <Card X.

R(P,Q) denotes the set of possibilistic removed sets for P and Q. According to the definition R(P,Q) = Min(Min(PR(P, Q), ≤w), ≤Card) and if P ⊔ Q is consistent then R(P, Q) = {∅}.

Example 3. (Example 1 continued) PR(P,Q) = {X1 = {r1 : (b ← not c, 0.9)},X2 = {r3 : (c ← not a, 0.8)}}, w(X2) < w(X1) therefore R(P, Q) = {X2}.

Let f be a selection function which chooses one removed set among the possible ones, the Possibilistic Removed Set Revision operator denoted by ⊛RSR(f) is a function from P× P to P defined as follows.

Definition 10. Let P,Q ∈ P with w(P) < 1, ∀r ∈ Q,

Note that if R(P,Q) = ∅ then ⊛RSR(f) is not defined. If P ⊔Q is consistent then R(P, Q) = {∅} thus P⊛RSR(f)Q = P ⊔ Q.

Example 4. (Example 1 continued) R(P,Q) = {{r3 : (c ← not a, 0.8)}} and P⊛RSR(f)Q = {r0 : (a ← not b, 1), r1 : (b ← not c, 0.9), r2 : (d ←, 0.8), r4 : (e ←, 0.7)}. Note that there is no unnecessary removal.

The following example illustrates several results of revision according to the chosen selection function.

Example 5. Let P and Q such that P = {r1 : (a ← not b, 0.9), r2 : (b ← not c, 0.9)} and Q = {r0 : (c ← not a, 1)}. We have ΠAS(P) = {{b}}, ΠAS(Q) =

{{c}}, ΠAS(P ⊔ Q) = ∅ and P ⊛Π Q = Q. However R(P,Q) = {{r1}, {r2}}. Let f1(R(P,Q)) = {r1} and f2(R(P, Q)) = {r2}, we have P⊛RSR(f1)Q = {r0, r2} and P⊛RSR(f2)Q = {r0, r1}.

4 Semantic Characterization

4.1 Standard Possibilistic ASP Base Revision

We first recall the semantic approach of possibilistic ASP [Nicolas et al., 2006] to deal with inconsistent programs. An inconsistency degree is defined in a semantic way, by using a possibilistic distribution.

This inconsistency degree is used to define a cut that computes the greatest (w.r.t. the certainty level of rules) consistent subprogram of P .

Definition 12. Let cut be the function defined from P to P by:

• cut(P) = P if SemInc(P) = 0
• cut(P) = cut(P>SemInc(P)) otherwise.

The following proposition gives the semantic counterpart of the ASP base revision operator ⊛Π.

Proposition 3. Let P,Q ∈ P such that w(P) < 1, ∀r ∈ Q, n(r) = 1 and Q is m-consistent.

This proposition directly follows from Definition 7 (P ⊛Π Q = (P ⊔ Q)>Inc(P⊔Q)) and from the result of [Nicolas et al., 2006]: let P ∈ P, cut(P) = P>Inc(P).

The following example illustrates the computation of the revised program by the cut function.

Example 6. (Example 1 continued) We recall that Q = {r0 : (a ← not b, 1)} et P = {r1 : (b ← not c, 0.9), r2 : (d ← , 0.8), r3 : (c ←not a, 0.8), r4 : (e ←, 0.7)}.

In the least specific possibility distribution, the greatest possibility degree is 0.2 and corresponds to four interpretations:

• A1 = {b}. Fal(P ⊔Q, A1) = {r2, r3, r4}, w(Fal(P ⊔ Q, A1)) = 0.8 and ˜π({b}) = 1 - 0.8 = 0.2.
• A2 = {b, d}. Fal(P ⊔ Q, A2) = {r3, r4}, w(Fal(P ⊔ Q, A2)) = 0.8 and ˜π({b, d}) = 0.2.
• A3 = {b, e}. Fal(P ⊔ Q, A3) = {r2, r3}, w(Fal(P ⊔ Q, A3)) = 0.8 and ˜π({b, e}) = 0.2.
• A4 = {b, d, e}. Fal(P ⊔ Q,A4) = {r3}, w(Fal(P ⊔ Q, A4)) = 0.8 and ˜π({b, d, e}) = 0.2.

The inconsistency degree is

The first cut removes r2, r3 and r4 and the resulting program (P ⊔ Q)>0.8 = {r0, r1} is consistent. Note that it matches with the revised syntactic program P ⊛Π Q.

The cut can be slightly harder to compute. Indeed, in the next example, two successive cuts are necessary to restore consistency.

Example 7. Let Q = {r1 : (a ← not d, 1), r2 : (a ← not b, 1)} et P = {r3 : (b ← not c, 0.9), r4 : (c ← not a, 0.8), r5 : (d ← not e, 0.7), r6 : (e ← not a, 0.6), r7 : (b ←, 0.5)}. The inconsistency of P ⊔Q comes from the rules {r1, r5, r6}. The inconsistency degree is 0.6. It corresponds to the interpretation A = {b, c, d} and Fal(P ⊔Q,A) = {r6}. But the first cut (P ⊔Q)>0.6 is inconsistent: the rule r6 is removed but also the rule r7 because its weight is lower (0.5). The removal of r7 creates a new inconsistency with the cycle {r2, r3, r4} which was initially "blocked" by r7. The inconsistency degree of (P ⊔ Q)>0.6 is 0.7. It corresponds to the interpretation A = {a, b} with Fal((P ⊔Q)>0.6,A) = {r5}. A second cut removes r5 and the resulting program (P ⊔ Q)>0.7 = {r1, r2, r3, r4} is consistent.

4.2 Possibilistic Removed Sets

We now present the semantic counterpart of the removed sets. It is based on the notions of preferred models and preferred falsified rules. In a possibility distribution for P ⊔Q, the preferred models are those with the greatest possibility degree. If all interpretations have a degree equal to zero then the set of preferred models is empty.

Definition 13 (preferred models). Let P,Q ∈ P, the set of preferred models PrefMod(P,Q) = {m ∈ Mod(Q) | ˜πP⊔Q(m) ̸= 0 and ∀m′ ∈ Mod(Q), ˜πP⊔Q(m′ ) ≤ ˜πP⊔Q(m)}.

Example 8. (Example 1 continued) In this example, A1 to A4 are the models of Q with the greatest possibility degree, thus P refMod(P, Q) = {A1, A2, A3, A4}.

Note that interpretations that are not models of Q have a degree of possibility equal to 0.

These models with the greatest possibility degree match with those for which the weight of the falsified rules is minimal. These sets of falsified rules are the "semantically preferred" ones (denoted by PrefFal(P,Q)) and the smallest (w.r.t inclusion and cardinality) of them correspond to the removed sets. The following proposition establishes this correspondence between syntactic and semantic definitions.

Proposition 4. Let P,Q ∈ P such that w(P) < 1, ∀r ∈ Q, n(r) = 1 and Q is m-consistent. Let PrefFal(P,Q) = {Fal(P ⊔ Q,m) | m ∈ PrefMod(P,Q)} be the sets of rules falsified by the preferred models,

Min(Min(P ref F al(P, Q), ⊆), ≤Card) = R(P, Q).

Sketch of proof. Let AllFal(P,Q) = {X | X = Fal(P ⊔ Q,m),m ∈ Mod(Q), ˜πP⊔Q(m) ̸= 0}. A first part of the proof establishes that ΠAS((P \ F al(P, m)) ⊔ Q)∗ = {m ∈ Mod(Q) | m ⊆ head(App((P ⊔Q)m,m)) and App((P ⊔ Q)m,m) is grounded}. This result allows one to link Definition 8 (of a potential removed set X based on the condition that (P \ X) ⊔ Q is consistent), and the semantic characterization based on the falsified rules in the models such that ˜πP⊔Q(m) ̸= 0 (see conditions in Definitions 5 and 6 of the possibility distribution). It is then established that PR(P,Q) = Min(AllFal(P,Q),⊆) and finally that Min(PR(P, Q), ≤w) = Min(P ref F al(P, Q), ⊆).

The following examples illustrate the semantic characterization of the removed sets.

Example 9. (Example 1 continued) PrefFal(P,Q) = {{r2, r3, r4}, {r3, r4}, {r2, r3}, {r3}} and Min(Min(PrefFal(P,Q),⊆),≤Card) = {{r3}} = R(P, Q).

Example 10. (Example 7 continued) Here, PrefMod(P, Q) = {{b, c, d}}, PrefFal(P, Q) = {{r6}} and Min(Min(PrefFal(P,Q),⊆),≤Card) = {{r6}} = R(P,Q). Note that the result is direct contrary to the standard possibilistic revision where two cuts are necessary.

The semantic characterization of ⊛RSR(f) immediately follows from the semantic characterization of the removed sets.

Furthermore if all rules of P have the same weight α ∈ ]0, 1[ then all the models of Q with a non-zero degree (˜πP⊔Q(m) ̸= 0) have the same degree 1 - α and the falsified rules corresponding to these models (the AllFal(P, Q) set from the proof sketch) match with the canonical removed sets from [Garcia et al., 2017]. Thus the present work is a generalization of the approach of [Garcia et al., 2017].

5 Logical Properties

In this section we go a step further in the characterization of Possibilistic ASP base revision by presenting logical properties of the proposed operators through a set of postulates. Hansson's postulates [Hansson, 1999] have been formulated to characterize belief base revision in a classical (monotonic) logic setting. We now adapt them within the non-monotonic possibilistic ASP framework.

Let P , Q, X, R ∈ P, and ⋆ be a revision operator.

Success Q ⊆ P ⋆Q.

Inclusion P ⋆Q ⊆ P ⊔Q.

Consistency P ⋆Q is consistent.

Vacuity

Relevance If P ⊔ Q is consistent then P ⋆ Q = P ⊔ Q.

If R ̸= ∅, R ⊆ P \p (P ⋆ Q) then (P ⋆ Q) ⊔ R is inconsistent.

Uniformity If for all subsets X of P, X ⊔Q is consistent if and only if X ⊔ R is consistent then P \p (P ⋆ Q) = P \p (P ⋆ R).

The meaning of the postulates is the following: Success gives priority to new information. Inclusion states that the union of the initial logic programs is the upper bound of any revision operation. Consistency expresses that the result of revision is consistent. Vacuity establishes that if the input is consistent with the initial logic program then nothing is removed from it. Relevance expresses the intuition that nothing is removed from the original logic program unless its removal contributes in some way to make the result consistent. Uniformity determines that if two consistent logic programs are consistent with the same subsets of the initial logic program P then the respective erased set of rules of P should be identical.

Proposition 5. ⊛Π satisfies Inclusion, Consistency and Vacuity but it does not satisfy Success, Relevance nor Uniformity.

Proof. By definition ⊛Π satisfies Inclusion, Consistency and Vacuity . Success: a counterexample is given in Example 2. Relevance: a counterexample is given in Example 1. We have P ⊛Π Q = {r0, r1}. Let R = {r4}, R ⊆ P \p (P ⊛Π Q) but (P ⊛Π Q) ⊔R = {r0, r1, r4} is consistent. This is due to the removal of rules that are not involved in inconsistency but for which the certainty degree is low.

Uniformity: we give a counterexample: P = {(a ← not b, 0.9), (c ← not a, 0.7), (e, 0.5), (f, 0.5)}, Q = {(e, 1), (b ←not c, 1)}, R = {(f, 1), (b ←not c, 1)}. We have P ⊛Π Q = {(e, 1), (b ← not c, 1), (a ← not b, 0.9)} and P ⊛Π R = {(f, 1), (b ← not c, 1), (a ← not b, 0.9)} thus P \p (P ⊛Π Q) = {(c ← not a, 0.7), (f, 0.5)} and P \p (P ⊛Π R) = {(c ← not a, 0.7), (e, 0.5)} therefore P \p (P ⊛Π Q) ̸= P \p (P ⊛Π R).

Proposition 6. If ⊛RSR(f) is defined, for any selection function f, ⊛RSR(f) satisfies Success, Inclusion, Consistency, Vacuity , Relevance, and Uniformity.

Sketch of proof. By definition if ⊛RSR(f) is defined, ⊛RSR(f) satisfies Success, Inclusion, Consistency and Vacuity.

Relevance: For any selection function f, we have P \p (P⊛RSR(f)Q) = P \p ((P \ f(R(P,Q))) ⊔ Q) = f(R(P,Q)) by definition of the operators ⊔ and \p , by the hypothesis w(P) < 1 and ∀r ∈ Q, n(r) = 1 and since f(R(P,Q)) is a removed set. Thus, for any selection function f, if R ⊆ P \p (P⊛RSR(f)Q) then R ⊆ f(R(P,Q)) and, by Definition 9, (P⊛RSR(f)Q) ⊔ R is inconsistent.

Uniformity : We can first easily prove that if for all subsets X of P , X ⊔ Q is consistent if and only if X ⊔ R is consistent then PR(P,Q) = PR(P,R). For any selection function f, we have P \p (P⊛RSR(f)Q) = f(R(P,Q)) and P \p (P⊛RSR(f)R) = f(R(P,R)). Since PR(P, Q) = PR(P, R) the result holds.

6 Complexity

We study the following complexity problem:

Name : ΠASPMODELCHECKING(RS)

Input : P, Q ∈ P , X ∈ A.

Question : ∃R ∈ R(P, Q) such that X ∈ ΠAS((P \R)⊔Q) ?

Proposition 7. ΠASPMODELCHECKING(RS) is in DP.

Proof. We recall that a language L is in the class DP if and only if there are two languages L1 ∈ NP and L2 ∈ coNP such that L = L1 ∩ L2 [Papadimitriou, 1994] 1 .

Finding such a set R can be broken down as follows: 1. Is there a set R ⊆ P such that X ∈ ΠAS((P \ R) ⊔ Q): (a) Guess a set of possibilistic normal rules R; (b) Check that R ⊆ P; (c) Check that X ∈ ΠAS((P \ R) ⊔ Q). 2. Compute kR = |R|. 3. Check that R ∈ R(P,Q): (a) Guess a set of possibilistic normal rules R0 and a set of possibilistic atoms X0; (b) Check that R0 ⊆ P; (c) Check that R0 <w R or (R0 =w R and |R0| < kR); (d) Check that X0 ∈ ΠAS((P \ R0) ⊔ Q).

1 The DP class is sometimes also called BH2.

The algorithmic difficulty concentrates in points 1 and 3. The algorithm described in point 1 can be solved in polynomial time on a non-deterministic Turing machine, and R is a certificate, because it succinctly proves that X ∈ ΠAS((P \ R) ⊔Q). Thus, this subproblem is in NP. In the algorithm described in point 3, (R0,X0) is a succinct disqualification, that is, it proves that X /∈ R(P,Q). This algorithm can run in polynomial time on a non deterministic Turing machine. Thus, it is in coNP.

Proposition 8. ΠASPMODELCHECKING(RS) is DPcomplete.

Sketch of proof. The proof is based on a transformation of the problem EXACTINDEPENDENTSET into two possibilistic normal logic programs P and Q, with a one to one correspondence between the possibilistic answer sets of this program and the maximal independent sets of size k of a graph G = (V,E). We recall the definition of the problem EXACTINDEPENDENTSET: Name : EXACTINDEPENDENTSET

Input : a graph G = (V, E), a positive integer k ≤ |V |.

Question : Does G contain an independent set of size k, i.e. a subset V ′ ⊆ V such that |V ′ | = k and such that no two vertices in V ′ are joined by an edge in E, such that there is no other independent set with a size k′ > k.

The program Q contains: (a) rules describing the graph vertices and edges, and (b) rules defining what an independent set is. The program P asserts that all the vertices of the graph form an independent set. In this context, removed sets represent sets of vertices which have to be dropped, so the remaining vertices form an independent set.

7 Conclusion

The paper addresses possibilistic ASP base revision with certain input. It proposes two revision operators. The first one, ⊛Π, is fully defined in the spirit of possibility theory while the second one ⊛RSR(f) stemming from "removed sets revision" keeps the rules not involved in inconsistency. For both revision operators a semantic characterization is provided in terms of a possibilistic distribution and logical properties are provided in terms of satisfaction of Hansson's postulates rephrased within the possibilistic ASP framework. Moreover the computational complexity of the ⊛RSR(f) operator is given.

There are several issues to address as future work. The first one is to study the complexity of the ⊛Π operator.

In this paper, all rules of the revising logic program are certain, thus a natural future work is to extend the proposed operators to the case where the input is uncertain, leading to the definition of semi-revision operators. A strategy has to be defined when the necessity degree of some rules in the revising program is lower than the one of the same rules appearing in the initial program.

Another issue is to investigate other revision strategies stemming from possibilistic revision or ASP base revision.

Finally, possibilistic ASP base revision could be investigated within the framework of other possibilistic ASP extensions.