# updating_the_belief_promotion_operator__f6562883.pdf

Updating the Belief Promotion Operator

Daniel A. Grimaldi1 , M. Vanina Martinez2,3 , Ricardo O. Rodriguez2,3

1UBA, FCEy N, Departamento de Matem atica 2UBA, FCEy N, Departamento de Computaci on 3UBA-CONICET, Inst. de Invest. en Cs. de la Computaci on grim.daniel@gmail.com, {mvmartinez, ricardo}@dc.uba.ar

In this note, we introduce the local version of the operator for belief promotion proposed by Schwind et al. in [Schwind et al., 2018]. We propose a set of postulates and provide a representation theorem that characterizes the proposal. This family of operators is related to belief promotion in the same way that update is related to revision, and we provide several results that allow us to show this relationship formally. Furthermore, we also show the relationship of the proposed operator with features of credibility-limited revision theory.

1 Introduction

Throughout her lifecycle, an agent is constantly receiving new information about herself and her environment. The way that she filters, summarizes and stores this new information is of critical importance for the quality of her decision making. There are many formal theories for representing the dynamic of integrating new information. Most of these formalizations of integrating information share the assumption that new information must be prioritized. In this paper, we focus on updating, and propose a new integration model where the new information is not necessarily prioritized. Our proposal is inspired by promotion operators, developed in [Schwind et al., 2018], in the sense that new information may not be completely accepted. Furthermore, our approach is dual to Booth et al. s from [Booth et al., 2012] where the new information is accepted only if it is a formula that belongs within the scope of a credibility limit from the old information. In our case, the new information determines a credibility-limited preservation of the existing one. In this work we study local promotion operators for the case where the information is represented in propositional logic, as done in the Katsuno and Mendelzon s framework [Katsuno and Mendelzon, 1990]. We propose a set of postulates and the corresponding representation theorem for local promotion operators. Next, we introduce an example that motivates our aim. Consider the following situation: One day Funes went to the supermarket, while his daughter Mafalda stayed alone at home. Steps away from coming back, he heard something

grim.daniel@gmail.com

like his mother s ornamental vase breaking, and thought to himself: Mafalda is alone, so if I find the vase broken, she is the only one who could have broken it . As Funes arrived to his home, Mafalda intercepted him and said: I didn t break nor saw grandma s vase. If you find it broken, it s because there is a ghost in the house . Until then, Funes was certain that ghosts did not exist. Operators such as revision and update modify belief theories prioritizing new information, however, in this case, this is not completely adequate as one would have to accept proposition Ghosts exist as a result. Promotion based on revision, on the other hand, allows to preserve some original beliefs that are close to new evidence, extending the way to represent belief change in a static world. However, it fails in this case too, because the world has changed, since, we have learned that grandma s vase is broken. This example shows the need of an alternative promotion operator, with the local properties of update operator where we would like to be able to accept that grandma s vase is broken and to preserve that ghosts do not exist. In Section 3 we further analyse this example in order to make clearer the differences among several models: revision, update, promotion, and our proposal. Due to space restrictions some of the proofs were moved to an Appendix (included as supplementary material).

2 Preliminaries

Our formal setting is finite propositional logic. Thus, we consider a set of formulas L built from a finite set V ar of propositional variables and the usual logical connectives. An interpretation I is a mapping that assigns a truth value to every variable from V ar. For any ϕ L, I is a model of ϕ, noted I |= ϕ iff I makes ϕ true in the usual truth functional way; and ϕ denotes the set of models of ϕ.

In [Katsuno and Mendelzon, 1990] the authors proposed a new kind of modifications for knowledge states, the socalled update operators. Intuitively, these operators consist of bringing the knowledge state up to date when the world described by it, changes. They provided a new set of postulates that apply to update and characterize all operators satisfying these postulates in terms of a set of partial orders defined over possible worlds. They use ψ µ to denote the result of updat-

Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence (IJCAI-21)

ing a knowledge base ψ with the sentence µ. The postulates for update are:

1. ψ µ |= µ.

2. If ψ |= µ then ψ µ ψ.

3. If ψ |= and µ |= then, ψ µ |= .

4. If ψ1 ψ2 and µ1 µ2 then, ψ1 µ1 ψ2 µ2.

5. (ψ µ) ν |= ψ (µ ν).

6. If ψ µ1 |= µ2 and ψ µ2 |= µ1 then, ψ µ1 ψ µ2.

7. If ψ is complete then, (ψ µ1) (ψ µ2) |= ψ (µ1 µ2).

8. (ψ1 ψ2) µ (ψ1 µ) (ψ2 µ).

The authors provide a model theoretic characterization of these postulates by means of pre-orders over the set of interpretations I. A pre-order on I is a reflexive and transitive relation. A pre-order is total if for all I and J interpretations, either I J or J I. They consider a function that assigns to each interpretation I a pre-order I over I. This assignment is faithful 1 if the following condition hold:

For all I,I I: if I = I then I <I I .

Let M be a subset of I. An interpretation J is minimal in M with respect to I if J M and there is no I M such that I <I J. Let min(M, I) be the set of all J M such that J is minimal in M with respect to I. Katsuno and Mendelzon established the following characterization of the update operators.

Theorem 2.1. An update operator satisfies conditions ( 1) ( 8) if and only if there exists a faithful assignment that maps each interpretation I to a partial pre-order I s.t.:

I ψ min ( µ , I)

There are two basic differences between revision and update from a model theoretic point of view. One is that revision is characterized by total pre-orders while update is defined from a family of partial pre-orders. However, it is also possible to build a class of update operators based on a family of total pre-orders, namely, when the postulates ( 6) and ( 7) are replaced by a new postulate:

9. If ψ is complete and (ψ µ) ν |= then, ψ (µ ν) |= (ψ µ) ν.

The second difference is that, in the case of update more than one order can be induced by each model of ψ, while for revision only one order can be induced. This local behaviour of update contrasts with the global behaviour of revision. The work in [Becher, 1999] extends updating for infinite languages and the notion of analytic revision is introduced as a framework for comparing update and revision.

1The term persistent was used in [Katsuno and Mendelzon, 1990], but it was replaced by faithful in [Katsuno and Mendelzon, 1991]

2.2 Promotion

The main goal of Schwind, Konieczny and Marquis belief promotion operator in [Schwind et al., 2018] is to give yet another perspective of non-prioritized revision with the following rationale: an agent may prioritize new information µ, but sometimes it will consider preserving some of its original beliefs ψ if they are close enough to the new data. In order to represent this behavior, noted as ψ µ, they adapted revision postulates, inspired by the symmetric postulates of Commutative revision and added a property of conditional ψ success:

If ((ψ ν) µ) ψ |= then (ψ µ) ψ |=

This postulate gives rise to the notion of trigger function, that will be further studied in this work.

Definition 2.2. A trigger function is a mapping σ associating any formula µ with a formula σ (µ) s.t. all formulas µ, µ :

1. µ |= σ (µ) (inclusion).

2. If µ µ then σ (µ) σ (µ ) (equivalence preserving).

The formula σ(µ) is used to establish which formulas are preservable according to µ, i.e. we are going to say that a formula ϕ is preservable with respect to µ, if ϕ σ(µ) = . This notion of preservable is dual to one of credible in [Booth et al., 2012]. This connection will be further developed in Section 7.

3 Local Promotion

In this section we describe our proposal, which takes the adaptation that belief promotion operator does to revision and adjusts it to update operators, maintaining the symmetric properties and the promotion postulate of conditional ψ success. The postulates for local belief promotion are:

1. ψ µ |= ψ µ.

2. If ψ |= µ then ψ µ µ ψ ψ.

3. If ψ |= and µ |= then (ψ µ) µ |= .

4. If ψ1 ψ2 and µ1 µ2 then, ψ1 µ1 ψ2 µ2.

5. (ψ µ) µ ν |= (ψ (µ ν)) (µ ν)

6. If (ψ µ1) µ1 |= µ2 and (ψ µ2) µ2 |= µ1 then (ψ µ1) µ1 (ψ µ2) µ2.

7. If ψ is complete then (ψ µ1) (ψ µ2) µ1 µ2 |= (ψ (µ1 µ2)) (µ1 µ2).

8. ((ψ1 ψ2) µ) µ ((ψ1 µ) (ψ2 µ)) µ.

9. (ψ µ) ψ ν |= ((ψ ν) µ) (ψ ν).

10. If (ψ1 µ) ψ1 |= ψ2 and (ψ2 µ) ψ2 |= ψ1 then (ψ1 µ) ψ1 (ψ2 µ) ψ2.

11. If µ is complete then (ψ1 µ) (ψ2 µ) ψ1 ψ2 |= ((ψ1 ψ2) µ) (ψ1 ψ2).

12. (ψ (µ1 µ2)) ψ ((ψ µ1) (ψ µ2)) ψ.

13. If ((ψ ν) µ) ψ |= then (ψ µ) ψ |= .

Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence (IJCAI-21)

These postulates are an adaptation of update postulates based in promotion. Postulates ( 1) ( 4) correspond directly to the first four update postulates, but considering nonpriorization in ( 1) and µ success in ( 3). The commutativity adaptation of ( 2) follows from the fact that KM revision postulate ( 2), that also appears in promotion, is commutative, but update postulate ( 2) is not. Since some sort of commutativity is mandatory in order to have non-prioritized operators, we need to explicitly define it. Postulates ( 5) ( 8) and ( 9) ( 12) correspond directly to the last four update postulates for each formula, respectively. This duplicity is forced in order to preserve the selected information from both formulas. ( 13) is the conditional ψ success property that originally appears in the promotion postulates. Proposition 3.1. A local promotion operator satisfies conditions ( 1) ( 13) if and only if there exist two update operators 1, 2 and a trigger function σ, such that for all formulas ψ and µ,

ψ µ (ψ 1 µ) (µ 2 (ψ σ (µ)))

Proof. (If) Let 1 and 2 be update operators, σ a trigger function, and an operator defined by ψ µ (ψ 1 µ) (µ 2 (ψ σ (µ))). We show that satisfies ( 1) to ( 13). The first four are directly satisfied. For the rest we first need to rewrite formulas (ψ µ) µ and (ψ µ) ψ, that appear from ( 5) to ( 8) and from ( 9) to ( 13) respectively. Since ψ (ψ µ) (ψ µ) and µ (ψ µ) ( ψ µ), applying ( 8) and then ( 2) to both update operators we have that ψ µ (ψ µ) ((ψ µ) 1 µ) ((µ ψ) 2 (ψ σ (µ))). Then, by ( 1), the definition of and ( 2) we have that:

(ψ µ) µ |= (((ψ µ) 1 µ) µ) (ψ µ) (ψ 1 µ)

(ψ µ) ψ |= (ψ µ) ((µ ψ) 2 (ψ σ (µ))) (µ 2 (ψ σ (µ)))

Therefore (ψ µ) µ ψ 1 µ and (ψ µ) ψ µ 2 (ψ σ (µ)). Now, postulates from ( 5) to ( 8) are directly satisfied by ( 5) to ( 8) of 1 and postulates from ( 9) to ( 12) are satisfied by applying the second equivalence and postulates ( 5) to ( 8) of 2, respectively. It only remains to prove postulate ( 13). Assume (ψ µ) ψ |= . Since, as shown above, (ψ µ) ψ µ 2 (ψ σ (µ)), then, we have that either µ |= or ψ σ (µ) |= by 3. If µ |= then µ |= ψ ν σ (µ), therefore (µ 2 (ψ ν σ (µ))) ψ µ ψ |= by ( 2). Otherwise (µ 2 (ψ ν σ (µ))) ψ |= σ (µ) ψ |= by ( 1). Hence (µ 2 (ψ ν σ (µ))) ψ |= . Also, ((ψ ν) 1 µ) ψ |= µ ψ by ( 1) and if ψ σ (µ) |= then ψ µ |= . Therefore ((ψ ν) 1 µ) ψ |= . Since ((ψ ν) µ) ψ (((ψ ν) 1 µ) ψ) ((µ 2 (ψ ν σ (µ))) ψ) we conclude that ((ψ ν) µ) ψ |= . (Only if) Let be an operator satisfying ( 1) to ( 13). Using ( 1), we can rewrite ψ µ:

ψ µ (ψ µ) (µ ψ) ((ψ µ) µ) ((ψ µ) ψ)

Let us first verify that operators 1 and 2 defined as:

ϕ 1 γ (ϕ γ) γ

ϕ 2 γ (γ ϕ) γ if (γ ϕ) γ |= or ϕ |= γ otherwise

are indeed update operators. Note that if ϕ |= then both operators satisfy all the update postulates. We remark the case of 2, because by ( 2) and its definition, we have that ϕ 2 γ (γ ϕ) γ ϕ γ . Therefore, for the following consider the case ϕ |= . Operator 1 satisfies postulate ( 1) by ( 1) and 2 by definition. To verify postulate ( 2), assume that ϕ |= γ. by ( 2) we know that ϕ γ ϕ and γ ϕ ϕ. Then ϕ 1γ (ϕ γ) γ ϕ γ ϕ and for ϕ 2γ we have that (γ ϕ) γ |= . Then ϕ 2 γ (γ ϕ) γ ϕ γ ϕ. Hence 1 and 2 satisfy ( 2). Similar direct proofs can be made to see that both operators satisfies ( 3) and ( 4). Also, 1 directly satisfies ( 5) to ( 8) by ( 5) to ( 8) respectively, as well as, 2 by ( 9) to ( 12) respectively, when the first condition is true. So we need to see the case when, in addition to ϕ |= , (γ ϕ) γ |= holds: ( 5) Since ϕ 2 γ γ, by ( 13) we have ((γ ν) ϕ) γ |= . Then ϕ 2 (γ ν) γ ν (ϕ 2 γ) ν. ( 6) Assume that ϕ 2γ1 |= γ2 and ϕ 2γ2 |= γ1. Combining this assumptions with postulates ( 13) and ( 9) it is easily deduced that (γ1 ϕ) γ1 |= if and only if (γ2 ϕ) γ2 |= . Then ϕ 2 γ1 γ1 γ2 ϕ 2 γ2. ( 7) Assume ϕ is complete and consider (ϕ 2 γ1) (ϕ 2 γ2). If at least one (γi ϕ) γi |= , then ((γi (γ1 γ2)) ϕ) γi |= by ( 13). And ((γ1 γ2) ϕ) γi |= ((γi (γ1 γ2)) ϕ) γi by ( 9). Therefore (γ1 γ2) ϕ |= γi and then we have that ((γ1 γ2) ϕ) (γ1 γ2) ((γ1 γ2) ϕ) γj with j = i. Then, ((γ1 γ2) ϕ) (γ1 γ2) |= γj and (γj ϕ) γj |= (γ1 γ2). Hence ((γ1 γ2) ϕ) (γ1 γ2) (γj ϕ) γj by ( 10). Moreover, we have that ϕ 2 γj |= ϕ 2 (γ1 γ2), satisfying ( 7) as wanted. ( 8) If at least one ϕi satisfies (γ ϕi) γ |= , then by ( 12) we have that (γ (ϕ1 ϕ2)) γ (γ ϕj) γ (ϕi 2 γ) ((γ ϕj) γ) with j = i. Therefore, γ 2 (ϕ1 ϕ2) (γ 2 ϕ1) (γ 2 ϕ2). Having shown that the operators satisfy the postulates, we now define a function σ such that:

σ (µ) = {I I : αI such that I |= (αI µ) αI}

where αI is the complete formula associated to interpretation I. We need to verify that σ is a trigger function. Let I be an interpretation of µ and αI its formula, then αI |= µ. By ( 2), we have that αI µ αI, and therefore, I |= σ (µ), satisfying condition 1 in Definition 2.2. Now let us show condition 2 by considering µ, µ such that µ µ and let I be an arbitrary interpretation. By ( 4), we have that (αI µ) αI (αI µ ) αI and, therefore, σ (µ) σ (µ). Next, we want to show that if (ψ µ) ψ |= then (ψ µ) ψ |= σ (µ). Let I |= (ψ µ) ψ and αI such that I |= αI |= (ψ µ) ψ. Since I |= (ψ µ) αI and

Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence (IJCAI-21)

I |= ψ αI, then by ( 9) we have that I |= (αI µ) αI, and therefore I |= σ (µ). Also, by ( 10) applied to (ψ µ) ψ |= ψ σ (µ) and ((ψ σ (µ)) µ) ψ σ (µ) |= ψ we have that (ψ µ) ψ ((ψ σ (µ)) µ) (ψ σ (µ)). Lastly, let us prove ψ µ (ψ 1 µ) (µ 2 (ψ σ (µ))). Note that if µ |= this holds trivially, so consider µ |= . Then, Our proof finishes by showing that if ((ψ σ (µ)) µ) (ψ σ (µ)) |= then ψ σ (µ) |= . Assume that ψ σ (µ) |= and let I |= ψ σ (µ). By definition of σ, we have I |= (αI µ) αI and I |= ψ σ (µ). Hence by ( 9), we get I |= ((ψ σ (µ) αI) µ) ψ σ (µ). Particularly ((ψ σ (µ) αI) µ) ψ σ (µ) |= . Therefore by ( 13) we have that ((ψ σ (µ)) µ) ψ σ (µ) |= , which lead us to a contradiction. As a result, we have shown that ψ σ (µ) |= .

Proposition 3.2. is a local promotion operator (i.e., it satisfies ( 1 13)) if and only if there exists a trigger function σ, and two total faithful assignments I 7 1 I and I 7 2 I, such that for all formulas ψ and µ:

I ψ min µ , 1 I S

I µ min ψ , 2 I

if ψ σ(µ) = .

I ψ min µ , 1 I otherwise.

Thus local promoting µ into ψ consists in (i) including some worlds of µ considering every world of ψ; and (ii) including some worlds of ψ provided that ψ is close enough to µ (where the admissible neighborhood of µ is made precise by σ) considering every world of µ. Let us see our local promotion operator in action. Come back to the Funes and Mafalda s example from the Introduction. Take the set of propositional variables V ar = {b, g, h, v} with the following meaning: b stands for Mafalda broke the vase . g stands for Ghosts exist . h stands for Mafalda was alone at home . v stands for The vase is broken . According to that, Funes and Mafalda s beliefs, namely ϕ and µ, can be represented respectively as h g (v b) and b g (v h). The next table shows the Hamming s distance between possible worlds, assuming a bit representation in alphabetical order:

ϕ 0010 1010 1011 0110 1 2 3 µ 0101 3 4 3 0100 2 3 4

For comparison purposes, let us calculate revision, promotion, update and local promotion with σ(µ) = : ϕ µ = {(0, 1, 1, 0)}, with revision Funes now believes that the vase is not broken and ghosts exist. ϕ µ = {(0, 1, 1, 0), (0, 0, 1, 0)}, with promotion Funes now believes that the vase is not broken but does not know whether ghosts exist or not.

ϕ µ = {(0, 1, 1, 0), (0, 1, 0, 1)}, with update Funes now believes that ghosts exist, that Mafalda did not break the vase and that the vase is broken if and only if Mafalda was not alone at home. ϕ µ = {(0, 1, 1, 0), (0, 1, 0, 1), (0, 0, 1, 0), (1, 0, 1, 1)} with local promotion Funes has now a more complex but reasonable belief: either ghosts exist, Mafalda did not break the vase and the vase is broken if and only if she was not alone at home or ghosts do not exist, she was alone at home and the vase is broken if and only if Mafalda broke the vase.

4 Properties Inherited from Update The representation theorem also shows us that promoting µ into ψ using extends µ-promotion in the same way update extends revision. For example, it is possible to characterize a class of local promotion operators based in total preorder as proposed in [Schwind et al., 2018], if we replace postulates ( 6) and ( 7) by postulate ( 14), and postulates ( 10) and ( 11) by postulate ( 15), respectively: 14. If ψ is complete and (ψ µ) (µ ν) |= then, (ψ (µ ν)) (µ ν) |= (ψ µ) (µ ν). 15. If µ is complete and (ψ µ) (ψ ϕ) |= then, ((ψ ϕ) µ) (ψ ϕ) |= (ψ µ) (ψ ϕ). Proposition 4.1. A local promotion operator which satisfies postulates ( 1) ( 5), ( 8) ( 9) and ( 12) ( 15), can be represented using total preorder update operators. Another interesting property of equivalence between update and revision appears whenever a theory K is fixed, as shown in [Peppas et al., 1996]. In order to obtain the same equivalence between local promotion and promotion, both formulas need to be fixed: Proposition 4.2. Let ϕ and µ be fixed L consistent formulas. Then, for every promotion operator there exists a Local promotion operator such that ϕ µ ϕ µ. Finally, we will show with a counter example that update monotony is not preserved in local promotion. If ϕ = p, ψ = q p, then ϕ |= ψ, and µ = p, σ(µ) = . Using Hamming s distance to define both update operators, we have:

ϕ µ p p ψ µ p (p q) p q

Nevertheless, it is worth noting that the following restricted version of update monotony does hold for local promotion:

If ϕ |= ψ then (ϕ µ) µ |= (ψ µ) µ

5 Properties Inherited from Promotion In the same sense of [Schwind et al., 2018], we can define the subclass of local-consensual promotion operator

by adding the following postulate to ( 1) ( 13):

16. If ϕ |= then (ϕ

Local consensual promotion is the king of promotion operators which gives the same priority to ϕ and µ. Technically, it forces that the trigger function to be equivalent to . It is worth noticing that consensual operators are yet asymmetric

Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence (IJCAI-21)

in the sense that the two underlying update operators involved according to Proposition 3.1 are potentially different. If we want to get commutative operators then the following property has to be required:

17. ϕ µ µ ϕ.

In addition, we are able to give an unnatural and elemental example of local-promotion operator: Definition 5.1 (Elemental Local Promotion Operator). The elemental local operator E is defined as:

ϕ E µ ϕ if ϕ |= µ ϕ µ otherwise

Note that this last operator is a little less general than the drastic promotion operator proposed in [Schwind et al., 2018], but it is clearly the weakest local promotion operator in the sense that for every ϕ and µ, any local operator satisfies ϕ µ |= ϕ E µ. Proposition 5.2. The elemental local operator E satisfies postulates ( 1) ( 13). In the end of this section, we show that local promotion is a generalization of update operator in the same way promotion is a generalization of revision. But we also characterize it, noting that these operators are equivalent when the local promotion satisfies 1 or its trigger function is the identity. Proposition 5.3. Let be an operator. The following statements are equivalent: 1. is an update operator. 2. is a local promotion with identity as the trigger function. 3. is a local promotion that satisfies 1.

6 Restriction on the Trigger Function In this section, we study extra properties that are suitable for the trigger function in the context of local promotion and how they, in combination with properties of the underlying update, influence the properties of the induced operator . As mentioned before, a trigger function has the role of choosing what part of the old information is preserved. In Subsection 2.2, we introduced some basic properties for the trigger functions, namely, inclusion and equivalence preserving. Now, we consider some additional conditions to those mentioned in Definition 2.2 such as:

3. If µ ν |= , then σ(µ ν) σ(µ) σ(ν) ( -distributivity). 4. If µ |= and µ |= ν, then σ(µ) |= σ(ν) (monotony).

It is easy to prove that -distributivity implies monotony and last one implies equivalence preserving. Now, we consider how these extra conditions impose new properties over the local promotion operator. Proposition 6.1. Let and σ be a local promotion operator and its trigger function, respectively. The following conditions are equivalent: 1. σ satisfies monotony. 2. satisfies the following postulate:

18. If µ |= ν, ψ ν |= , and (ψ ν) |= ν, then (ψ µ) |= µ.

Postulate 18 expresses that if ψ is preserved by a formula µ, then ψ is preserved for all consequences of µ.

Proposition 6.2. Let and σ be a local promotion operator and its trigger function, respectively. The following conditions are equivalent:

1. σ satisfies -distributivity.

2. satisfies the following postulate:

19. If ψ is a complete formula and µ ν |= , then (ψ µ) (ψ ν) ψ ψ (µ ν) ψ.

Postulate 19 says that if an interpretation Iψ is independently preserved by formulas µ and ν whose conjunction is consistent, then Iψ is preserved for their conjunction as well. In this section, we proposed additional properties over a trigger function, extending Definition 2.2 and obtaining their associated characterizations. In the next section, we analyze a more general notion of trigger that establishes a connection with credibility-limited operators [Garapa et al., 2020].

7 Credibility Limited Promotion

In this section, we would like to discuss the relationships between local promotions operators and another kind of operators that allow softer changes than revision operators: credibility limited (CL) revision operators. For that, let us rewrite the result from Proposition 3.2, so it gives us an alternative definition of a local promotion operator as follows:

ϕ µ = ϕ 1 µ µ 2 ϕ if ϕ σ(µ) = ϕ 1 µ otherwise.

In this way, our local promotion operator can be seen as a CL revision operator which is induced by two (standard) updating operators and a sentence pointing out to what is considered credible. But conceptually, the behavior is a little different and it deserves to be discussed in more detail. In a CL revision, whenever a new sentence µ is credible, it is added to the set of beliefs of the agent as a consequence of the revision process; otherwise, no change is made to the belief set. On the other hand, in the case of local promotion, the sentence µ is always accepted but its inclusion is moderated by the part of the previous belief set which is credible according to µ. In this sense, we can see the second updating operator 2 (in the breaking of Proposition 3.2) as a local CL revision operator which satisfies some interesting properties that we will discuss below. However, in order to do that we need to drop out the conditions over the trigger function described in Definition 2.2. We will call such functions, naked trigger functions, i.e. we associate each sentence µ with an arbitrary credibility formula σ(µ), however, we use it in same way according to Proposition 3.1. It is worth noting that if the range of the mapping σ is just { , }, then we have the limit case where for each formula µ either everything or nothing of the old information is preserved. We will now analyze possible desirable properties for our naked trigger function, that will create different alternative behaviors for the local promotion operators. Some of these

Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence (IJCAI-21)

properties were already considered in [Garapa et al., 2020]. We start with a quite natural one:

Preserving consistency: If µ is consistent, then σ(µ) is too. The following one is a particular case of this property:

Credibility Lower Bounding:

If µ is consistent, then µ |= σ(µ)

It is worth remarking that credibility lower bounding is also a particular case of inclusion in Definition 2.2. In this sense, for the operators considered in this paper the credibility depends on the new information, while in CL revision, the credibility is assessed independently of the existing information and the new one, i.e. it is rather fixed a priori. In [Garapa et al., 2020], they propose the following minimality property:

Closure Under Double Negation:

µ L : σ(µ) σ( µ)

We can extend this to require that, regarding credibility, logically equivalent sentences have the same status:

Credibility of Logical Equivalents ([Hansson et al., 2001]):

µ1, µ2 L : If µ1 µ2, then σ(µ1) σ(µ2)

Note that last property is the same as equivalence preserving in Definition 2.2. Another interesting property in relation to disjunction states that if two sentences are not credible, then their disjunction is not credible:

Disjunctive Completeness ([Hansson et al., 2001]):

µ1, µ2 L : σ(µ1 µ2) σ(µ1) σ(µ2)

All the previous properties are called internal in [Garapa et al., 2020] in the sense that they only describe conditions on σ, and, hence, only over µ that is the second parameter of the local promotion operator. The next ones are called external as they also take into account the first parameter of the local promotion operator, i.e., ϕ, or describe properties over the behavior of the local promotion operator itself. For instance, the following property states that if a sentence µ is consistent with another one ϕ, then the first sentence must be credible:

Expansive Credibility ([Hansson et al., 2001]):

If ϕ |= µ, then µ |= σ(µ)

Another reasonable requirement is that any sentence in the outcome of a local promotion ( ) by a credible sentence is also credible.

Revision Credibility ([Hansson et al., 2001]):

If µ |= σ(µ), then ϕ µ |= σ(µ)

Finally, a stronger requirement can be introduced which states that if a sentence µ is not credible, then the local promotion ϕ µ will preserve a formula (that together with ϕ) implies µ:

Strong Expansive Credibility ([Garapa et al., 2020]):

If µ |= σ(µ), then (ϕ µ) ϕ |= µ

In this section, we have only rewritten some interesting properties over the trigger function that are consistent with the notion of credibility proposed by Hansson in [Hansson et al., 2001]. Note however, that we have not studied how such properties affect the local promotion operator in terms of satisfaction of postulates. A deeper analysis of these issues, including an axiomatic characterization of each mentioned property, is out of the scope of this paper and is left for a future work.

8 Conclusion and Future Works In this paper we have presented local promotion operators, a new class of belief change operators, together with a series of representation theorems that characterize them in terms of preorders over interpretations. This is a local version of the promotion operator ([Schwind et al., 2018]) in the same sense that updating is a local version of revision. In fact, we have found a natural generalization of all representation theorems in [Schwind et al., 2018]. For instance, it is shown that local promotion can be reproduced with the aid of two update operators and the trigger function σ. We would like to complete our paper mentioning some future works: 1. Study the erasure operator [Katsuno and Mendelzon, 1991] associated to local promotion. 2. Extend the local promotion operator in the sense of [Konieczny and P erez, 2008]. 3. Study the relation between postulates of credibilitylimited local promotion operator and properties over the trigger functions. 4. Analyse how local promotion is related to selective revision in [Ferm e and Hansson, 1999]. It might be possible because some of the properties introduced in Section 7 are also closely related to the properties of transformation function used in the definition of selective revision operators. 5. Consider an iterated version of local promotion operator by using the ideas in [Ferm e and Gonc alves, 2016].

Acknowledgements Martinez was partially supported by Facultad de Ciencias Exactas y Naturales, UBA (RESCS-2020-345-E-UBA-REC), by Universidad Nacional del Sur (UNS) under grant PGI 24/ZN34, and Agencia Nacional de Promoci on Cient ıfica y Promoci on Tecnol ogica under grant PICT-2018-0475 (PRHPIDRI 2014-0007). Rodriguez acknowledges partial support of Argentinean projects: PICT-2019-2019-00882, UBA-Cy T20020190100021BA and PIP 112-2015-0100412 CO. We are grateful to the referees that read the first version of the paper and pointed out one crucial mistake in the results of Section 3. They also helped us to reorganize and correct the paper.

Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence (IJCAI-21)

References [Becher, 1999] Ver onica Becher. Binary Functions for Theory Change. Ph D thesis, Department of Computer Science of Buenos Aires University, Buenos Aires, 9 1999. [Booth et al., 2012] Richard Booth, Eduardo Ferm e, S ebastien Konieczny, and Ram on Pino P erez. Credibilitylimited revision operators in propositional logic. In Proceedings of the Thirteenth International Conference on the Principles of Knowledge Representation and Reasoning, pages 116 125, Rome, Italy, June 2012. AAAI Press. [Ferm e and Gonc alves, 2016] Eduardo Ferm e and Sara Gonc alves. On the iteration of km-update. In Christoph Beierle, Gerhard Brewka, and Matthias Thimm, editors, Computational Models of Rationality, Essays dedicated to Gabriele Kern-Isberner on the occasion of her 60th birthday, pages 243 264. College Publications, 2016. [Ferm e and Hansson, 1999] Eduardo Ferm e and Sven Ove Hansson. Selective revision. Studia Logica, 63:331 342, 1999. [Garapa et al., 2020] Marco Garapa, Eduardo Ferm e, and Maur ıcio Reis. Credibility-limited base revision: New classes and their characterizations. Journal of Artificial Intelligence Research, 69:1023 1075, November 2020. [Hansson et al., 2001] Sven Ove Hansson, Eduardo Ferm e, John Cantwell, and Marcelo Falappa. Credibility limited revision. The Journal of Symbolic Logic, 66(4):1581 1596, 2001. [Katsuno and Mendelzon, 1990] Hirofumi Katsuno and Alberto O. Mendelzon. Propositional knowledge base revision and minimal change. Artificial Intelligence, 52(3):263 294, December 1990. [Katsuno and Mendelzon, 1991] Hirofumi Katsuno and Alberto O. Mendelzon. On the difference between update a knowledge base and revising it. In Proceedings of the Second International Conference on Principles of Knowledge Representation and Reasoning, pages 387 394, San Francisco, CA, USA, April 1991. Morgan Kaufmann. [Konieczny and P erez, 2008] S ebastien Konieczny and Ram on Pino P erez. Confluence operators. In Proceedings of the eleventh European conference on logics in artificial intelligence, pages 272 284, Berlin, Heidelberg, Germany, September 2008. Springer-Verlag. [Peppas et al., 1996] Pavlos Peppas, Abhaya C. Nayak, Maurice Pagnucco, Norman Y. Foo, Rex Bing Hung Kwok, and Mikhail Prokopenko. Revision vs. update: Taking a closer look. In Proceedings of the 12th European Conference on Artificial Intelligence, pages 95 99, Budapest, Hungary, August 1996. John Wiley and Sons, Chichester. [Schwind et al., 2018] Nicolas Schwind, S ebastien Konieczny, and Pierre Marquis. On belief promotion. In Proceedings of the Sixteenth International Conference on Principles of Knowledge Representation and Reasoning, pages 297 307, Tempe, Arizona, USA, November 2018. AAAI Press.

Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence (IJCAI-21)