A Unified Framework of Propositional Knowledge Base Revision and Update Based on State Transition Models

1 Introduction

Belief revision [Alchour´ron et al., 1985] and belief update [Katsuno and Mendelzon, 1992] are two of the most basic types of belief change operations. When we accept new information into the current belief, we need to estimate whether the new information represents more reliable information about a static world, or it reports some (unspecified) change occurred in a dynamic world. This estimation causes decision making to select either revision to fix some errors in the current belief, or update to reflect some change into the belief.

In this paper, we introduce a state transition model as a unified framework of belief revision and belief update. The state transition model illustrates prior knowledge for estimation about the background of the new information, and also provides a selection mechanism for the decision making. Using the state transition model, we also propose a hybrid operation, called acceptance, of revision and update.

2 Knowledge Base Revision and Update

Katsuno and Mendelzon [Katsuno and Mendelzon, 1991] have rephrased the AGM postulates for revision [Alchour´ron et al., 1985], and have provided a possible worlds characterization of revision. For a given propositional sentence KB that represents the current knowledge base, and a propositional sentence α that represents new information about a static world, KB ◦α denotes a revision of KB by α. Revision operators are characterized by postulates (R1) - (R6).

(R1) KB ◦ α |= α.

• (R2) If KB ∧α is satisfiable, then KB ◦ α ≡KB ∧α.

Graduate School of Information Science and Technology Hokkaido University murahiko@main.ist.hokudai.ac.jp

• (R3) If α is satisfiable, then KB ◦ α is also satisfiable.
• (R4) If |= α↔ β, then KB ◦ α ≡KB ◦ β.
• (R5) (KB ◦ α) ∧ β |=KB ◦ (α∧ β).
• (R6) If (KB ◦ α) ∧ β is satisfiable, then KB ◦ (α ∧ β) |= (KB ◦ α) ∧ β.

Katsuno and Mendelzon [Katsuno and Mendelzon, 1992] have proposed a general characterization of belief update. For a given knowledge base KB and a sentence α that represents new information by some (unspecified) change in a dynamic world, KB ⋄ α denotes an update of KB by α. Update operators are characterized by postulates (U1) - (U8).

• (U1) KB ⋄ α |= α.
• (U2) If KB |= α, then KB ⋄ α ≡KB.
• (U3) If both KB and α are satisfiable, then KB ⋄ α is also satisfiable.
• (U4) If |= α↔ β, then KB ⋄ α ≡KB ⋄ β.
• (U5) (KB ⋄ α) ∧ β |=KB ⋄ (α∧ β).
• (U6) IfKB⋄α |= β andKB⋄β |= α, thenKB⋄α ≡KB⋄β.
• (U7) If KB is complete, then (KB⋄α)∧(KB⋄β) |=KB⋄ (α ∨ β).
• (U8) (KB1 ∨KB2) ⋄ α ≡ (KB1 ⋄ α) ∨ (KB2 ⋄ α).

3 State TransitionModels

We introduce a state transition model as prior knowledge for estimation about the background of the new information. State transition models are closely related to event models for abductive characterization of belief update [Boutilier, 1996].

Definition 1 A state transition model is a triple 〈W, T,≼〉, where W is a non-empty set of possible worlds, T ⊆ W × W is a non-empty set of state transitions, and ≼ is a total preorder on T .

(x, y) ∈ T is a state transition from the starting point x to the terminal y. The intuitive meaning of (x, y) ∈ T is "we know that some (unspecified) change at x may cause the situation y". The total preorder ≼ illustrates relative plausibility of state transitions. If we have (x, y) ≼ (u, v), we interpret that (x, y) is at least as plausible as is (u, v). Using the state transition model, we can represent the following two criteria about relative plausibility of possible worlds:

• Comparing (x, y) and (u, v) such that x ̸= u: the relative plausibility of x and u as the actual world.
• Comparing (x, y) and (x, v) with the same starting point x: the relative plausibility of y and v as the result of some change at x.

Definition 2 For any R ⊆ T, we define Sp(R) ⊆ W and Ter(R) ⊆W as follows, respectively:

If R = ∅, we define Sp(R) = Ter(R) = ∅.

For any X ⊆ W and Y ⊆ W, we define (X, Y ) ⊆ T by:

If either X = ∅ or Y = ∅, we define (X, Y ) = ∅. For any singleton {w} ⊆ W, we abbreviate ({w}, X) and (X, {w}) as (w,X) and (X,w), respectively.

Definition 3 Let STM be a state transition model. STM is called centered iff the following two conditions hold:

1. For each world w ∈W, (w,w) ∈ T.
2. For any non-empty subset X ⊆ W and any w ∈ X, the loop (w,w) is the minimum element in (w,X), that is, if (w, x) ∈ (w, X) and x ̸= w, then (w, w) ≺ (w, x).

Using the given state transition model, the current knowledge base KB is semantically characterized by starting points of the most plausible state transitions in T .

Definition 4 Let STM be a state transition model. A knowledge base KB induced by STM is a propositional sentence such that

4 Acceptance: AHybrid Operation of Revision and Update

Using the given state transition model that illustrates prior knowledge for estimation, we provide a selection mechanism to decide we use either revision or update when we accept new information. Explainability of the new information we define below is the key concept of such decision making.

Definition 5 Let STM be a state transition model, and KB is a knowledge base induced by STM. A sentence α is explainable by STM iff (w, ∥α∥) ̸= ∅ for all w ∈ ∥KB∥.

We have the following simple selection strategy by explainability of the new information: Let CSTM = 〈W, T, ≼〉 be a centered state transition model, and KB be the current knowledge base induced by CSTM. For any observation α,

1. If α is explainable by CSTM, we regard α as the new information by some change, and update KB by α.
2. Otherwise, we regard α as more reliable information about a static world, and revise KB by α.

According to the selection strategy, we introduce a hybrid operation of revision and update, called acceptance, based on the given centered state transition model CSTM. We use KB ✁ α to denote the result of acceptance of α into KB. The symbol ✁ is called an acceptance operator. We intend to have either KB ✁ α ≡ KB ◦ α or KB ✁ α ≡ KB ⋄ α based on explainability of α by CSTM.

Theorem 1 Let CSTM be a centered state transition model, KB be a knowledge base induced by CSTM, and ✁ be an acceptance operator defined by the following equation:

1. If α is explainable by CSTM, then ✁ satisfies postulates (U1) - (U4), the following weakened (U5):

(U5w) If α ∧ β is explainable, then (KB ⋄ α) ∧ β |= KB ⋄ (α ∧ β), postulates (U6), (U7), and a postulate (U9) proposed by Boutilier [Boutilier, 1996]: (U9) If KB is complete, (KB⋄α) ̸|= ¬β andKB⋄α |= γ, then KB ⋄ (α∧ β) |= γ.

1. If α is not explainable by CSTM, then ✁ satisfies postulates (R1) - (R6).

The acceptance operator ✁ is well-defined as a revision operator ◦ when α is not explainable by CSTM. On the other hand, ✁ does not satisfy (U8) when α is explainable. However, in equation (5), α is independently evaluated in each possible world w ∈ ∥KB∥, therefore the idea of semantic characterization of KM update [Katsuno and Mendelzon, 1992] is illustrated in this framework.

Acknowledgement

We would like to thank the anonymous reviewers for helpful comments and suggestions.