R-Mod: Minimal Structural Revision of S5 Epistemic Models

Abstract

Revising what an agent knows in response to new information is a central problem in formal epistemology. In doxastic logics such as KD45, belief revision proceeds by reordering plausibility: the agent simply re-ranks which worlds it considers most credible. This strategy fails for S5 knowledge. Because knowledge is factive (Kφ → φ), an agent cannot come to know phi merely by finding φ-worlds more plausible; if the actual world falsifies φ, then Kφ remains unsatisfiable regardless of any reordering. Accommodating new modal information in S5 therefore requires genuine model transformation: adjusting the equivalence-based accessibility structure, the valuation, or both.

We develop R-Mod, a selection-based revision operator that realizes this transformation as minimal structural repair. Given an S5 model and a target formula, R-Mod searches for a closest model, measured by a bisimulation-aware distance on quotient structures, that satisfies the formula while preserving S5 constraints. At the skeptical level, R-Mod satisfies success, consistency preservation, and deductive closure; classical AGM postulates such as Inclusion and Superexpansion fail due to permissible structural amplification, though we identify conditions under which they re-emerge. Computationally, the decision problem is NP-complete, and we provide tractable fragments exploiting structural locality.

While recent work has advanced AGM-style postulate analysis for S5 and topological semantics via simplicial complexes, these approaches do not provide goal-driven optimization with algorithmic guarantees. R-Mod fills this gap by combining modal invariance, explicit distance minimization, and fine-grained complexity analysis. Our results reframe revision in S5 as knowledge-model revision rather than belief revision, offering a foundation for algorithmic implementations and extensions to richer epistemic semantics.