Research map / Learning theory and algorithms / Combinatorial and search optimization
Minimal Change in Modal Logic S5
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Extends AGM/KM belief revision to modal logic S5 with three modal postulates (M1-M3), lexicographic set pseudo-distances over pointed S5 models, and shows that the sum-based distance Dsum satisfies all postulates while using strict implication avoids the p∧q vs p∧(p→q) collapse.
Problem
Belief revision in the AGM tradition has not been adequately extended to modal sentences; existing operations do not handle minimal change when modalities are present, and AGM syntax-insensitivity is criticized for treating p∧q and p∧(p→q) identically.
Approach
Lift Dalal's Hamming-distance revision to S5 by using a lexicographic order on pointed S5 models, where set-level pseudo-distances (Hausdorff, injection-based, sum-based) are compared first and actual-world distance second; new axioms A3-A5 on pseudo-distances guarantee the modal postulates M1-M3, with Dsum satisfying all of them.
Key results
- Proposition 15: the sum-based revision *Dsum satisfies (M1)-(M3), while *Dhaus and *Dinj satisfy only (M1) and violate (M2) and (M3).
- Proposition 3 and Table 1: Dsum satisfies axioms A3-A5, Dhaus violates A4, and Dinj violates A4 and A5.
- Example 16: with strict implication, p∧q *Dsum ¬q and p∧(p≻q) *Dsum ¬q yield different outcomes, addressing the syntax-sensitivity criticism.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use the sum-based pseudo-distance Dsum instead of Dhaus or Dinj | S5 modal revision · S5 modal revision postulates | postulate satisfaction | Helped |
| Use Dhaus instead of Dsum | S5 modal revision · S5 modal revision postulates | M2 satisfaction | Hurt |
| Use Dinj instead of Dsum | S5 modal revision · S5 modal revision postulates | M3 satisfaction | Hurt |
| Use Dsum instead of Dhaus or Dinj | Set pseudo-distance construction · Set pseudo-distance axioms | A4 satisfaction | Helped |
| Use Dsum instead of Dinj | Set pseudo-distance construction · Set pseudo-distance axioms | A5 satisfaction | Helped |
Surprising findings
- Language splitting (Parikh's principle) fails for *Dsum, and revision outcomes depend on the chosen set of variables Var.
Limitations
- Only the logic S5 is treated; extension to K, S4 or other logics is non-trivial
- No complete axiomatic characterisation of the operation is given
- Dhaus and Dinj fail to satisfy M2 and M3 and Dsum's outcome depends on the variable set
Experimental setup
Baselines: Dhaus-based revision Dinj-based revision Caridroit et al. revision
Builds on: AGM postulates KM postulates Dalal revision Hausdorff distance Katsuno-Mendelzon faithful assignment
Closest papers by meaning
- An Alternative Theory of Stable Revision for Nondeterministic Approximation Fixpoint Theory and the Relationships (AAAI 2025 · similarity 0.87)
- On the Logic of Theory Base Change: Reformulation of Belief Bases (AAAI 2025 · similarity 0.86)
- A Modal Logic of Optimality (Student Abstract) (AAAI 2025 · similarity 0.83)
- A Variable Occurrence-Centric Framework for Inconsistency Handling (AAAI 2025 · similarity 0.83)
- Sound Over-Approximation of Equational Reasoning with Variable-Preserving Rules Parameterized by Derivation Depth (AAAI 2025 · similarity 0.83)
- An Algebraic Notion of Conditional Independence, and Its Application to Knowledge Representation (AAAI 2025 · similarity 0.83)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.