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).
Given a set , we will denote by () the power set of
, i.e. the set of all subsets of . Given a set a binary
relation ⪯ on is:
- reflexive if and only if ⪯ for all ∈ ;
- transitive if and only if it holds that if ⪯ and ⪯ ,
then ⪯ , for all , , ∈ ;
- antisymmetric if and only if it holds that if ⪯ and
⪯ , then = , for all , ∈ .
- total if and only if ⪯ or ⪯ for all , ∈ .
- irreflexive if and only if ̸≺ , for all ∈ .
- a pre-order if it is reflexive and transitive.
- an order if it is a pre-order which is also antisymmetric.
- a strict order if it is irreflexive and transitive. 1
The study of user profiles and their dynamics over time - a total strict order ≺ on if and only if it is a strict order
has gained increasing attention in the field of information and it holds that if ̸= , then ≺ or ≺ , for all
technology [
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 ∈ Γ }.
We note that if ⪯ is a total pre-order, then (Γ , ⪯ ) = { ∈ Γ : ⪯ , for all ∈ Γ }.
Definition 1. [
context).2
[
Definition 3. [
A well-formed formula (wff) of ℒL is defined by: 1. Every atomic formula of ℒL is a wff of ℒL.
≪ 1, 2, ..., ≫ be a tuple ( ∨ ), ( → ) and ( ↔ ).
a set of labels.
[
For each ∈ {1, ..., }, let be so under the following conditions: the domain associated with the label .
A profile
= ⟨1, 2, ..., ⟩ is said to satisfy a formula , denoted by |= , if it can be shown inductively to do 3. |= ( ∧ ) iff |= and |= ; 4. |= ( 1. |= ( = ) iff = ; 2. |= (¬ ) iff ̸|= ; iff |= or |= ; 5. | = ( → ) iff ̸|= or |= ; 6. |= (
↔ ) iff ( |= iff |= ). denote that is a tautology. ‖ ⊥ ‖ = ∅ 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 binary relation on PL. Γ -faithful if it satisfies:
[
We will use ⪯ as an abbreviations of ⪯ { }. We will also write -faithful instead of { }-faithful. Note that if ≺ is a strict order on PL, then the first condition of Definition 5 follows trivially, since ≺ is irreflexive, and the second condition can be rewritten as ≺ for all ∈ PL ∖ { }. 2Note that PL is finite.
=1 ⊥ (symbol to represent a contradiction); 6. ¬, ∧, ∨, →, that for all sentences : ︂{ (punctuation symbols); 4. , , ... (elements of ⋃︀ ); 5. if there is a P-faithful total strict order ≺ on PL, , such 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.
[
1, 2, ..., ≫ tuple of labels and let be a profile associated with An operator ⊙ is a PtoP profile revision on if and only be a ≪ ≪
An axiomatic characterizations for PtoP profile
revision operators has been presented in [
We say that is a model of if and only if |= . if there exists a Γ -faithful pre-order ⪯ Γ on PL, such that, 2.2.2. Model 2. From a Set of Profiles to a Set of ∨ ) revising a set of profiles.
We now present a model which addresses the problem of
[
Profiles operator ⊙ for all sentences : Γ ⊙ = ︂{
Γ
The operator ⊙ denoted by ⊙ ⪯ Γ
.
otherwise defined as presented above will be
In [
. among others, the following postulates: (SP1) If ‖ ‖ ̸= ∅, then Γ ⊙ ⊆ ‖ ‖. (SP2) If ‖ ‖ = ∅, then Γ ⊙ = Γ . (SP5) If Γ ∩ ‖ ‖ ̸= ∅ then Γ ⊙ = Γ ∩ ‖ ‖.
3.1. Model 1. From One Profile to One
In this subsection we characterize operators ⊙ and formulas which satisfy certain sets of one or more equations of Observation 7. Let L =≪ 1, 2, ..., ≫ be a tuple of labels. Let ∈ N1 and 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 =1 Observation 8. Let L =≪ 1, 2, ..., ≫ be a tuple of labels. Let ∈ N1 and for all ∈ {1, . . . , } let Γ and Φ be non-empty subsets of PL such that it holds that the form ⊙ = where and are, respectively, the inicial and the final profiles of an agent.
Observation 1. Let L =≪ 1, 2, ..., ≫ be a tuple of labels and let ∈ PL. Let ⊙ : ℒL → PL be a profile revision operator on that satisfies (P1), (P2) and (P3).
It holds that ⊙ = if and only if ‖ ‖ = ∅ or ∈ ‖ ‖.
Observation 2. Let L =≪ 1, 2, ..., ≫ be a tuple of labels, ∈ N1, and {1, . . . , } ∪ {1, . . . , } ⊆ PL. For each ∈ {1, . . . , } let ⊙ : ℒL → PL be profile revision operators on that satisfy (P1), (P2) and (P3). If for all ∈ {1, . . . , } it holds that ⊙ = and ̸= , then {1, . . . , } ⊆ ‖ ‖ ⊆ PL ∖ {1, . . . , }. either Γ ∩ Φ = ∅ or Φ ⊆ Γ .
If ⋃︀ Φ ⊆ ‖ ‖ ⊆ ⋂︀ (Φ ∪ PL ∖ Γ ), then, for all
=1 =1 ∈ {1, . . . , }, there exists a SPtoSp profile revision Observation 3. Let L =≪ 1, 2, ..., ≫ be a tu- operator ⊙ on Γ such that Γ ⊙ = Φ . ple of labels, ∈ N1, and {1, . . . , } ⊆ PL. If {1, . . . , } ⊆ ‖ ‖ ⊆ PL ∖ {1, . . . , }. Then for all ∈ {1, . . . , } there exists a PtoP profile revision operator ⊙ on such that ⊙ = .
Observation 9. Let L =≪ 1, 2, ..., ≫ be a tuple of labels, Γ and Φ be non-empty subsets of PL and Φ ̸= PL.It holds that either (i) there exists a formula and a SPtoSP profile revision operator ⊙ such that Γ ⊙ = Φ , Observation 4. Let L =≪ 1, 2, ..., ≫ be or (ii) there exist formulas 1 and 2 and SPtoSP profile a tuple of labels, ∈ N1, and {1, . . . , } ∪ revision operators ⊙ 1 and ⊙ 2 such that (Γ ⊙ 1 1) ⊙ 2 {1, . . . , } ⊆ PL be such that ̸= for all 2 = Φ . ∈ {1, . . . , }.
For each ∈ {1, . . . , } let ⊙ ≺ be a PtoP profile revision operator on . It holds that, ∀ ∈ {1, . . . , } ⊙ ≺ =
iff {1, . . . , } ⊆ ‖ ‖ ⊆ ⋂︀ (Ω ∪ {}).
=1 Where Ω = { ∈ PL : ≺ }. 3.2. Model 2. From a Set of Profiles to a
Set of Profiles In this subsection we present a study similar to the one carried in the previous subsection, but concerning profile revision operators on sets of profiles (rather than on single profiles).
Observation 5. Let L =≪ 1, 2, ..., ≫ be a tuple of labels and let Γ be a non-empty subset of PL. Let ⊙ : ℒL → (PL) be a profile revision operator on Γ that satisfies (SP1), (SP2) and (SP5). It holds that Γ ⊙ = Γ if and only if ‖ ‖ = ∅ or Γ ⊆ ‖ ‖.
Observation 6. Let L =≪ 1, 2, ..., ≫ be a tuple of labels and let Γ be a non-empty subset of PL, and Φ ⊂ Γ . Let ⊙ : ℒL → (PL) be a profile revision operator on Γ that satisfies (SP1), (SP2), (SP3) and (SP5).
It holds that Γ ⊙ = Φ if and only if Γ ∩ ‖ ‖ = Φ and Φ ̸= ∅.
Observation 10. Let L =≪ 1, 2, ..., ≫ be a tuple of labels. Let ∈ N1 and 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 an SPtoSP profile revision operator on Γ .
It holds that, ∀ ∈ {1, . . . , } Γ ⊙ ⪯ Γ = Φ
iff ⋃︀ Φ ⊆ ‖ ‖ ⊆ =1 ⋂︀ (Ω ∪ Φ ) =1 where Ω = { ∈ PL : ≺ Γ , for some ∈ Φ }.
User profiles are important tools in several areas of information technology. Given a profile, sometimes it is necessary to determine a set of tasks, or pieces of training which can transform the profile of a user into a target proifle. In this paper, we have characterized the solutions of “systems of equations" (or single equations) of the form G ⊙ = F, where G and F are, respectively, the initial and final sets of profiles or single profiles of an agent and ⊙ and are the “unknowns" (that we wish to determine). Acknowledgements We thank the reviewers of NMR 2023 and also the reviewers of KR2023 and the reviewers of ENIGMA-23 for their comments on previous versions of this paper, which have contributed to its improvement. This paper was partially supported by FCTFundação para a Ciência e a Tecnologia, Portugal through project PTDC/CCI-COM/4464/2020. E.F. was partially supported by FCT through project UIDB/04516/2020 (NOVA LINCS). M.G. and M.R. were partially supported by the Center for Research in Mathematics and Applications (CIMA), through the grant UIDB/04674/2020 of FCT.