User profiles are an essential Knowledge Representation tool in several areas of information technology. In a recent paper, Fermé et al. presented a formal framework for representing user profiles and profile revision operators defined through a Knowledge-Driven perspective. In this paper, we analyse the possibility of going from one given user profile to another by means of a profile revision operator. More precisely, given two profiles and we present some conditions which ensure that there is a profile revision operator ⊙ on and a sentence such that ⊙ = . Furthermore, considering a fixed operator ⊙ , we characterize the change formulas which are such that ⊙ = , by identifying upper and lower bounds for their sets of models. Analogous results are obtained for the case of a “system of equations" ⊙ = for every ∈ {1, . . . , }. Furthermore, a similar study is carried out considering profile revision operators defined on sets of profiles (which take sets of profiles to sets profiles rather than a single profile to a single profile).
The study of user profiles and their dynamics over time
has gained increasing attention in the field of information
technology. User profiles are widely used in various areas,
including recommendation systems [
In this paper, we expand the work presented in [
The rest of the paper is organized as follows: In Section 2, we introduce the notations and recall the main background concepts that will be needed throughout this article. In Section 3 we conduct the study mentioned above. In Section 4 we briefly mention other works related to the one presented in this paper. In Section 5 we summarize the main results obtained and point out some topics for future research.
Definition 1. [
To express properties of a profile (and therefore the
possibility of changing it), we need to define a formal
language:
Definition 2. [
L that we will consider is:
A non-strict pre-order is a reflexive and transitive relation. A non-strict order is a non-strict pre-order which is also antisymmetric. Given a non-strict pre-order ⪯ on a set , the associated strict part ≺ is defined by ≺ if and only if ⪯ and ̸⪯ , for all , ∈ . ⋍ will be used to denote that ⪯ and ⪯ .
Given a set a strict order ≺ on is an irreflexive (i.e, ̸≺ , for all ∈ ) and transitive relation on .1 A strict order is total if and only if it holds that either ≺ , ≺ or = for all , ∈ . Throughout the text, whenever we refer to pre-orders (respectively, orders) without mentioning whether or not they are strict, we will be referring to non-strict pre-orders (respectively, non-strict orders).
Let A be a set and Γ be a finite subset of A. Given a total strict order ≺ on A, the minimum of Γ with respect to ≺ is denoted by (Γ , ≺ ) and is defined as follows:
= (Γ , ≺ ) iff ∈ Γ and ≺ for all ∈ Γ ∖ { }.
Given a pre-order ⪯ on A, the set of minimal elements of Γ with respect to ⪯ is denoted by (Γ , ⪯ ) and is defined as follows: (Γ , ⪯ ) = { ∈ Γ : ̸≺ , for all ∈ Γ }.
(Γ , ⪯ ) = { ∈ Γ : ⪯ , for all ∈ Γ }.
In this subsection, we present the formal definition of a profile and introduce appropriate language and semantics for formalizing the dynamics of profiles. 1Every irreflexive and transitive relation on a set is also antisymmetric. 1. 1, 2, ..., (labels); 2. = (symbol of equality) 3. (,) (punctuation symbols);
4. , , ... (elements of ⋃︀ );
=1 5. ⊥ (symbol of contradiction); 6. ¬, ∧, ∨, →, ↔ (symbols of connectives).
Definition 3. [
An atomic formula in ℒL is defined by: if is a label occurring in L and ∈ , then = is an atomic formula of ℒL.
A well-formed formula (wff) of ℒL is defined by: 1. Every atomic formula of ℒL is a wff of ℒL. 2. If and are wffs of ℒL, so are (¬), ( ∧ ), ( ∨ ), ( → ) and ( ↔ ).
In the following definition we recall from [
Definition 4. [
We say that is a model of if and only if |= . The set of models of is denoted by ‖ ‖. It holds that . A set of profiles Γ is said to satisfy if and only if every profile in Γ is a model of . We say that is a tautology if and only if ‖ ‖ = PL. We will use |= to
The following definition introduces the notion of Γ faithful pre-order. Γ -faithful if it satisfies: Definition 5.
[
2. If ∈ Γ and ∈ PL ∖ Γ , then ≺ Γ .
If Γ is a singleton, say { }, then we will omit the braces in the subscript of the binary relation mentioned in the above definition by writing ⪯ instead of ⪯ will also write -faithful instead of { }-faithful. Note { }. We that if Γ =
{ }, and ≺ is a strict order on PL, then the ifrst condition of Definition 5 follows trivially, since is irreflexive, and the second condition can be rewritten ≺ as ≺ for all ∈ PL ∖ { }. 2.2.1. Model 1. From One Profile to One Profile In this subsection we present the first model for profile dynamics. In this model, we revise a profile by a formula of the language obtaining as output a profile.
Definition 6.
[
⟨, 1⟩. Consider the P-faithful total strict order ⟨, 1⟩ ≺ ⟨, 1⟩ ≺ ⟨, 2⟩ ≺ ⟨, 2⟩ ≺ ⟨, 3⟩ ≺ ⟨, 3⟩. Let be the sentence 1 = and be the sentence 2 = 2. It holds that ⊙ ≺ = ⟨, 1⟩ and ⊙ ≺ = ⟨, 2⟩. 2.2.2. Model 2. From a Set of Profiles to a Set of
Profiles We now present a model which addresses the problem of revising a set of profiles. A non-singular set of profiles of a given agent provides only partial information about that agent. For example, the following set of profiles {⟨25, , ⟩, ⟨25, , ⟩} that the agent is a 25 years old man but we do not know if expresses he is single or married.
Definition 7.
[
1, 2, ..., ≫ such that for all sentences : of labels and let Γ be a non-empty subset of PL. Let ⪯ Γ be a Γ -faithful binary relation on PL. The ⪯ Γ-based SPtoSP profile revision on Γ is the operator ⊙ ⪯ Γ : ℒL → (PL) be a tuple
In this section we present definitions and axiomatic characterizations of some operators of profile revision. Given a profile (respectively, a set of profiles Γ ) we shall designate by profile revision operator (or simply by profile regarding those operators: each sentence associates a profile (respectively, a set of profiles), which we shall denote by ⊙ (respectively Γ ⊙ ). Then, we find answers to the following questions formula which confirms it?
(i) Does it hold that, for any two user profiles 1 and 2 (respectively, sets of profiles Γ 1 and Γ 2), there exists a profile revision operator ⊙ and a formula such that 1 ⊙ = 2 (respectively, Γ 1 ⊙
= Γ 2)? (ii) When 1 and 2 (respectively, Γ 1 and Γ 2) are such that the answer to question (i) above is positive for a certain (fixed) operator ⊙ , how can we obtain a change for all sentences : revision induced by ≺ is the operator ⊙ ≺ such that revision) on (respectively, on Γ ) a function ⊙ that to (iii) Given profiles 1, . . . , , 1, . . . , (respectively, sets of profiles
Γ 1, . . . , Γ , Φ 1, . . . , Φ ), are there profile revision operators ⊙ 1, . . . , ⊙ and a sentence such that for each ∈ {1, . . . , }, it holds that ⊙ (iv) = (respectively, Γ ⊙
= Φ )?
When 1, . . . , , 1, . . . , (respectively, which confirms it? Γ 1, . . . , Γ , Φ 1, . . . , Φ ) are such that the answer to question (iii) above is positive for a certain (fixed) operators ⊙ 1, . . . , ⊙ , how can we obtain a change formula
The following postulates, which are based on the modified
version of the AGM revision postulates and the update
will be useful towards the axiomatic characterization of
the profile revision operators.
postulates proposed by Katsuno and Mendelzon [
= ⊙ . (P5) If ⊙ |= and ⊙ |= , then ⊙ = ⊙ . ‖ ‖ ⊆ PL ∖ { }. (P6) ⊙ ( ∨ ) = ⊙ or ⊙ ( ∨ ) = ⊙ .
Postulate P1 states that any consistent new information will be satisfied by the outcome.
P2 asserts that if the new P3 states that if the input is already inferred from the information is contradictory, then no change is performed. (P2) and (P3). starting profile, then no change occurs.
P4 expresses the principle of irrelevance of the syntax. Postulate P5 states that if the outcome of revising a profile
by
implies and the outcome of revising that profile by
implies , then the outcomes of those two revisions are
identical. This condition appears as (U6) in KM-update
[
We now present an axiomatic characterization for profile revision operators.
Observation 1. [
It holds that ⊙
= if and only if ‖ ‖ = ∅ or (P2) and (P3).
Proof. Assume that it holds that ‖ ‖ ̸= ∅. Hence by (P1) it follows that ∈ ‖ ‖. The other direction follows by
The following observation establishes a necessary condition, regarding the models of , to ensure that ⊙ = , where ̸= and ⊙ is an operator, on , that satisfies (P1), (P2) and (P3).
Observation 3. Let L = 1, 2, ..., ≫
be a tuple of labels and let , ∈ PL be distinct profiles. Let ‖ ‖ ⊆ PL ∖ { }. satisfies (P1), (P2) and (P3). If ⊙
= , then ∈ Proof. If ‖ ‖ = ∅, then by (P2) it follows that = .
Contradiction. Hence ‖ ‖ ̸= ∅. By (P1) it follows that ∈ ‖ ‖ . Let ∈ ‖ ‖
. If = , then by (P3) it follows that = . Contradiction. Hence ̸= . Thus
The following corollary establishes a necessary condition, regarding the models of , to ensure that is a solution of the system of equations of the form ⊙ where for each ∈ {1, . . . , }, and are distinct profiles and ⊙ is an operator, on , that satisfies (P1),
= , Corollary 1. Let L = ≪ labels and let {1, . . . , }∪{1, . . . , } ⊆ each ∈ {1, . . . , } let ⊙ : ℒL → PL be profile revision operators on that satisfy (P1), (P2) and (P3). If for
PL. For all ∈ {1, . . . , } it holds that ⊙
= and ̸= , then {1, . . . , } ⊆ ‖ ‖ ⊆ PL ∖ {1, . . . , }. be a relation on PL such that, for all , ∈ {1, . . . , } it { ∈ PL : ≺ }.
(SP1) If ‖ ‖ ̸= ∅, then Γ ⊙ ⊆ ‖ ‖.
Proof. Let Ω = { ∈ PL : ≺ }. (SP2) If ‖ ‖ = ∅, then Γ ⊙ = Γ . (⇒) Assume that ⊙ ≺ = . It holds that ̸= (SP3) Γ ⊙ ̸= ∅. and ⊙ ≺ is a PtoP profile revision operator on . Thus (SP4) If ‖ ‖ = ‖ ‖, then Γ ⊙ = Γ ⊙ . ‖ ‖ ̸= ∅. Hence (‖ ‖, ≺ ) = . Thus ∈ ‖ ‖. (SP5) If Γ ∩ ‖ ‖ ̸= ∅ then Γ ⊙ = Γ ∩ ‖ ‖. Let ∈ ‖ ‖. We will consider two cases: (SP6) Γ ⊙ ( ∨ ) = Γ ⊙ or Γ ⊙ ( ∨ ) = Γ ⊙ Case 1) = . Thus ∈ Ω ∪ {}. or Γ ⊙ ( ∨ ) = Γ ⊙ ∪ Γ ⊙ . Case 2) ̸= . Thus ∈ ‖ ‖ and ̸= = (SP7) Γ ⊙ ( ∨ ) ⊆ Γ ⊙ ∪ Γ ⊙ . (‖ ‖, ≺ ). Thus ≺ . Hence ∈ Ω . (SP8) If Γ ⊙ |= and Γ ⊙ |= , then Γ ⊙ = Γ ⊙ . In both cases it holds that ‖ ‖ ⊆ Ω ∪ {}. (⇐) Let ∈ ‖ ‖ ⊆ Ω ∪ {}. Hence ‖ ‖ ̸= ∅. We will (SP9) Γ ⊙ ∩ Γ ⊙ ⊆ Γ ⊙ ( ∨ ). consider two cases: Case 1) ‖ ‖ = {}, then by (P1) it follows that ⊙ ≺ (SP1), (SP2), (SP4) and (SP8) are the adapted versions = . of (P1), (P2), (P4) and (P5) respectively. (SP3) states Case 2) ‖ ‖ ̸= {}. Hence {} ⊂ ‖ ‖. It holds that that the outcome is always consistent. (SP5) corresponds ‖ ‖ ⊆ Ω ∪ {}. Let ∈ ‖ ‖ ∖ {}. Hence ∈ Ω . to the AGM revision postulate vacuity and states that Hence ≺ . Thus = (‖ ‖, ≺ ). Therefore if there are profiles in Γ that satisfy the input sentence ⊙ ≺ = . , then the output of the revision of Γ by is the set formed by those profiles. The intuition behind (SP6) is
The following corollary presents a result similar to that if we wish to revise by a disjunction and there is that illustrated in Observation 5, but where a system of some preference between the disjuncts, then this revision equations is considered. is equivalent to revising by the preferred disjunct. In the Corollary 3. Let L =≪ 1, 2, ..., ≫ be a tuple of case of indifference, revising by the disjunction returns labels and let {1, . . . , } ∪ {1, . . . , } ⊆ PL be the set of profiles consisting of the union of the revision such that ̸= for all ∈ {1, . . . , }. by each of the disjuncts. (SP7) states that if the revision
For each ∈ {1, . . . , } let ⊙ ≺ be a PtoP profile of a set of profiles Γ by ∨ leads to the acceptance of
revision operator on . It holds that, a profile , then the same should happen when revising
{1, . . . , } ⊆ ‖ ‖ ⊆
⋂︀ (Ω ∪ {}).
=1
Observation 6. [
The following observation states that when revising a set of user profiles Γ by a formula , through an operator that satisfies some of the postulates introduced above, the set of user profiles stays unchanged iff has no models or contains all the profiles in Γ .
The following observation states the bounds (in terms of set inclusion) of the models of a change formula in order to obtain a given set of profiles Φ as output of a revision of a set profiles Γ by .
Observation 10. Let L =≪ 1, 2, ..., ≫ be a tuple of labels. Let Γ be a non-empty subset of PL. Let ⊙ : ℒL → (PL) be a profile revision operator on Γ that satisfies (SP1), (SP2) and (SP5). If Γ ⊙ = Φ and Φ ̸⊆ Γ , then Φ ⊆ ‖ ‖ ⊆ PL ∖ Γ .
Proof. Assume that ⊙ satisfies (SP1), (SP2) and (SP5) and Γ ⊙ = Φ and Φ ̸⊆ Γ . By (SP2) it follows that ‖ ‖ ̸= ∅. Thus by (SP1) it yields that Φ ⊆ ‖ ‖. On the other hand, it holds that Γ ⊙ ̸= Γ ∩ ‖ ‖. Thus, by (SP5), Γ ∩ ‖ ‖ = ∅. Therefore, Φ ⊆ ‖ ‖ ⊆ PL ∖ Γ .
It follows from the above observation that, if its preconditions are held, then ‖ ‖ is unique whenever Φ = PL ∖Γ .
The following example illustrates the usefulness of the result of the above observation.
Example 3. Let PL = {1, 2, 3, 4, 5}, Γ = {2, 3}, Φ 1 = {1, 4} and Φ 2 = {1, 2}. Hence PL ∖ Γ = {1, 4, 5}. It holds that Φ 1 ̸⊆ Γ and
The following three corollaries follow from Observation 10.
Corollary 4 states that if Γ and Φ are two nonempty sets of profiles such that Φ is not contained in Γ , and Φ is obtained from Γ when revising it by through a SPtoSP profile revision operator, then Φ and Γ are disjoint sets of profiles.
Proof. (⇐) If ‖ ‖ = ∅, then by (SP2) it follows that Γ ⊙ = Γ . Assume now that ‖ ‖ ̸= ∅ and Γ ⊆ ‖ ‖.
Then, Γ ∩ ‖ ‖ = Γ ̸= ∅. Thus, by (SP5), it follows that Γ ⊙ = Γ . (⇒) Assume that Γ ⊙ = Γ . Consider that ‖ ‖ ̸= ∅.
Hence, by (SP1), it follows that Γ ⊙ ⊆ ‖ ‖. Thus Γ ⊆ ‖ ‖.
Observation 8. Let L =≪ 1, 2, ..., ≫ be a tuple of labels and let Γ be a non-empty subset of PL. Let Φ 2 ̸⊆ Γ . ⊙ : ℒL → (PL) be a profile revision operator on Γ that If Γ ⊙ = Φ 1, then {1, 4} ⊆ ‖ ‖ ⊆ { 1, 4, 5}. satisfies (SP1), (SP2) and (SP5). It holds that Γ ⊙ = Γ Thus either ‖ ‖ = {1, 4} or ‖ ‖ = {1, 4, 5}. if and only if ‖ ‖ = ∅ or Γ ⊆ ‖ ‖. There is no sentence such that Γ ⊙ = Φ 2 since, although Φ 2 ̸⊆ Γ , it cannot hold that {1, 2} ⊆ ‖ ‖ ⊆ {1, 4, 5}.
Given a set of profiles Γ , the following observation illustrates the properties that a change formula must satisfy in order for it to hold that Γ ⊙ = Φ , for a given set of profiles Φ ⊂ Γ .
Corollary 4. Let L =≪ 1, 2, ..., ≫ be a tuple of labels. Let Γ and Φ be non-empty subsets of PL such that Φ ̸⊆ Γ . Let ⊙ : ℒL → (PL) be a profile revision Observation 9. Let L =≪ 1, 2, ..., ≫ be a tuple operator on Γ that satisfies (SP1), (SP2) and (SP5). If of labels and let Γ be a non-empty subset of PL, and Γ ⊙ = Φ , then Φ ∩ Γ = ∅. Φ ⊂ Γ . Let ⊙ : ℒL → (PL) be a profile revision operator on Γ that satisfies (SP1), (SP2), (SP3) and (SP5).
The following corollary establishes upper and lower It holds that Γ ⊙ = Φ if and only if Γ ∩ ‖ ‖ = Φ and bounds for the set of models of formulas that are solutions Φ ̸= ∅. of a “system of equations" of the form Γ ⊙ where for each , Φ ̸⊆ Γ ̸= ∅ and ⊙ satisfies (SP1), shown above).
= Φ , that ⪯ Γ if = (since ⪯ Γ is reflexive, as =1 labels. For each ∈ {1, . . . , } let Γ be a non-empty subset of PL and ⊙ : ℒL → (PL) be a profile revision operator on Γ that satisfies (SP1), (SP2) and (SP5). If, for all ∈ {1, . . . , }, it holds that Γ ⊙ = Φ and Φ ̸⊆ Γ , then ⋃︀ Φ ⊆ ‖ ‖ ⊆ PL ∖ ⋃︀ Γ .
=1
We will now prove that ⪯ Γ is transitive. Let , , ∈ PL be such that ⪯ Γ and ⪯ Γ we intend to prove that ⪯ Γ .
It follows trivially if = or = . It also follows Where ⪯ Γ is such that ⪯ Γ iff either: (i) ∈ Γ or follows that ̸∈ (‖ ‖, ≺ Γ). Contradiction.
Case 1) ∈ Φ .
Case 1.1) ∈ Γ . Hence Φ Therefore ∈ Γ . Hence, by definition of ⪯ Γ, it follows that ⪯ Γ .
Case 1.2) ̸∈ Γ . Hence, by definition of ⪯ Γ, it follows Case 2) ̸∈ Φ . Then ∈ PL ∖ Γ . Hence ̸∈ Γ ∪ Φ .
Thus, by definition of ⪯ Γ, it follows that ⪯ Γ .
Thus in all cases it follows that ⪯ Γ . Hence ̸≺ Γ . It yields that ∈ ‖ ‖. Thus Φ ⊆
(‖ ‖, ≺ Γ).
Let ∈ (‖ ‖, ≺ Γ) and assume towards a contradiction that ̸∈ Φ . Let ∈ Φ ⊆ ‖ ‖. From ∈ (‖ ‖, ≺ Γ) it follows that ∈ ‖ ‖ ⊆ Φ
∪ PL ∖ Γ .
Thus ̸∈ Γ ∪ Φ . Therefore, ⪯ Γ . Furthermore it holds that ̸⪯ Γ . Hence ≺ Γ . From which it ∩ Γ ̸ = ∅
. Thus Φ ⊆ Γ .
The following example clariefis the importance of the condition “either Γ ∩ Φ =
∅ or Γ ⊆ Φ " included in the hypothesis of the statement of the previous observation. and Φ = Φ ∪ PL ∖ Example 4. Let PL = {1, 2, 3, 4}, Γ =
{1, 2} {1, 3}. Hence Γ ∩ Φ ̸
= ∅ and Φ ̸⊆ Γ . Let be a formula such that ‖ ‖ = Φ . Hence Φ ⊆ ‖ ‖ ⊆ Γ . However, since Γ
∩ ‖ ‖ ̸= ∅ it follows by Γ ⊙ = Γ ∩ ‖ ‖ = {1} ̸= Φ . (SP5) that for any SPtoSP profile revision operator ⊙ ,
Given sets of profiles Γ 1, . . . , Γ , Φ 1, . . . , Φ , the following corollary, which follows directly from Observation ∪ Φ . Hence ⪯ Γ . 11, establishes the bounds, in terms of set inclusion, for the models of in order to ensure the existence of a SP- be such that ‖ 2‖ = Φ . It holds that (PL ∖Φ) ∩Φ = ∅ and toSP revision operator ⊙ on Γ such that Γ ⊙ = Φ Φ ⊆ ‖ 2‖ ⊆ Φ ∪ PL ∖ (PL ∖ Φ) . Hence by Observation =1 ∅ orΦ ⊆ Γ .
If ⋃︀ Φ ⊆ ‖ ‖ ⊆ =1 for all ∈ 1, . . . , .
Corollary 7. Let L = ≪ of labels. For all ∈ {1, . . . , } let Γ and Φ be nonempty subsets of PL such that it holds that either Γ ∩Φ =
= Φ . However, as the following observation asserts, it is always possible, by means of a procedure of (at most) two-steps to transform a non-empty set of profiles Γ into any non-empty set of profiles Φ ̸= PL. Φ ̸= PL.4 It holds that either: Observation 12. Let L = ≪ Γ , therefore it is not possible to apply ⊙ 1 to the in general, ⊙ 1 ̸= ⊙ 2. outcome of Γ ⊙ 1 (unless Γ = Γ
⊙ 1 ). Hence, Proof. Case 1) Γ ∩ Φ =
∅ or Φ ⊆ Γ . Let be such that Φ ⊆ ‖ ‖ ⊆ Φ ∪ PL ∖ Γ . Then according to Observation 11 there exists a SPtoSP profile revision operator ⊙ such that Γ ⊙
= Φ . cases: Case 2) Γ ∩ Φ ̸
= ∅ and Φ ̸⊆ Γ . By hypothesis it holds that Φ ̸
= PL, Γ ̸= ∅ and Φ ̸= ∅. We will consider two Φ ̸⊆ Γ ).
Case 2.2) Γ ∖ Φ = Case 2.1) Γ ∖Φ ̸= ∅. Let 1 be such that ‖ 1‖ = Γ ∖Φ . It holds that Γ ∖ Φ ⊆ Γ and Γ ∖ Φ ⊆ ‖ 1‖ ⊆
(Γ ∖Φ) Hence by Observation 11 there exists a SPtoSP profile revision operator ⊙ 1 such that Γ ⊙ 1 1 = Γ ∖ be such that ‖ 2‖ = Φ . It holds that Γ ∖
Φ ∩ Φ = Γ ⊙ 1 1) such that (Γ ⊙ 1 1) ⊙ 2 2 = Φ . Φ ⊆ ‖ 2‖ ⊆ Φ
∪ PL ∖ (Γ ∖ Φ) . Hence by Observation 11 there exists a SPtoSP profile revision operator ⊙ 2 (on Φ . Let 2
∅ and ∅. Hence Γ ⊆ Φ . Thus Γ ⊂ Φ (since Let 1 be such that ‖ 1‖ = PL ∖Φ . It holds that PL ∖Φ ̸= ∅, Γ ∩PL ∖Φ = ∅ and PL ∖Φ ⊆ ‖ 1‖ ⊆ (PL ∖Φ)
∪PL ∖Γ .
Hence by Observation 11 there exists a SPtoSP profile 4If Φ = PL and Γ = PL the result also holds. Γ ⊙ 1 1) such that (Γ ⊙ 1 1) ⊙ 2 2 = Φ . 11 there exists a SPtoSP profile revision operator ⊙ 2 (on
Given two sets of profiles Γ and Φ , and a revision operator ⊙
on Γ induced by a specific (known) that: pre-order ⪯ , the following observation establishes the upper and lower bounds for the set of models of a change formula for it to hold that Γ ⊙ = Φ .
Observation 13. Let L = ≪ ∪PL ∖Γ . ∈ Φ ⊆ ‖ ‖ such that ≺ Γ . Contradiction since we need to prove that Φ = (⇐) From Φ ̸ = ∅ it follows that ‖ ‖ ̸= ∅
. Hence, (‖ ‖, ⪯ Γ). Let ∈ (‖ ‖, ⪯ Γ). It holds that ∈ ‖ ‖ ⊆ Ω
∪ Φ . Suppose towards a contradiction that ̸∈ Φ . Hence ∈ Ω .
Thus there exists ∈ Φ ⊆ ‖ ‖ such that ≺ Γ .
Contradiction, since ∈ (‖ ‖, ⪯ Γ). Hence ∈ Φ , from which it follows that (‖ ‖, ⪯ Γ) ⊆ Φ .
Let ∈ Φ ⊆ ‖ ‖ and suppose towards a contradiction that ̸∈ (‖ ‖, ⪯ Γ). Hence there exists a ∈ (‖ ‖, ⪯ Γ) such that ≺ Γ . Thus, by hypothesis, ̸∈ Φ . Hence ∈ Ω . Thus there exists ∈ (‖ ‖, ⪯ Γ). (⇒) If ‖ ‖ = ∅, then Γ ⊙ ⪯ Γ
diction. Hence ‖ ‖ ̸= ∅ . Let ∈ ‖ ‖ = Φ = Γ
. Contra. Assume that ̸∈ Φ . We intend to prove that ∈ Ω . From ̸∈ Φ it follows that ̸∈ (‖ ‖, ⪯ Γ). Hence there exists ∈ (‖ ‖, ⪯ Γ) = Φ such that ≺ Γ . Thus ∈ Ω . On the other hand it holds that Φ ⊆ ‖ ‖
.
The following corollary presents a result similar to that illustrated in Observation 13, but where a system of equations is considered (rather than a single equation).
Corollary 8. Let L =≪ 1, 2, ..., ≫ be a tuple of labels. For ∈ {1, . . . , } let Γ and Φ be two distinct non-empty subsets of PL. For ∈ {1, . . . , } let ⪯ Γ be a Γ -faithfull pre-order on Γ such that it holds that ̸≺ Γ , for all , ∈ Φ . Let ⊙ ⪯ Γ be a ⪯ Γ based SPtoSP profile revision operator on Γ . It holds that, ∀ ∈ {1, . . . , } Γ ⊙ ⪯ Γ = Φ
iff
⋃︀ Φ ⊆ ‖ ‖ ⊆
=1
⋂︀ (Ω ∪ Φ )
=1
a desirable change, although the two are related problems
(e.g., [
In this scenario, it is considered that is unknown, and that, for each agent, its previous beliefs and those obtained after the revision by are known. The authors characterized the set of formulas satisfying these requirements.
where Ω = { ∈ PL : ≺ Γ , for some ∈ Φ }.
User profiles are important tools in several areas of in
We close this section remarking that an SP-to-SP revi- formation technology. Given a profile, sometimes it is sion operator defined on a singleton is similar to a P-to-P necessary to determine a set of tasks, or pieces of training revision operator. However, we chose to treat these opera- which can transform the profile of a user into a target tors as distinct because they have conceptual differences. profile. In this paper, we provided a formal analysis of In P-to-P revision, the output is always a profile, while in the process of changing a user profile (or a set of proSP-to-SP revision, the output is a set of profiles, which ifles) into a target profile (or set of profiles) by means of may not be a singleton, even if the operator is defined on a profile revision operator, and we identified upper and a singleton. lower bounds for the set of formulas that cause such a change. Analogous results are obtained for “systems of equations" of the form ⊙ = and Γ ⊙ = Φ 4. Related Works (for every ∈ {1, . . . , }). This work may have some pratical applications.
To the best of our knowledge there are not many works
that relate belief revision with user’s profiles. One of those (a) Given a set of previous and current profiles of
works is [