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.

Abstract We study announcement synthesis under incomplete initial beliefs for multiple agents, instantiated with Dalal’s distance-based AGM revision. We introduce and formalize two semantics for the limited-knowledge propositional announcement problem: an optimistic variant (PAP$^{\exists }_{*_{D}}$), which requires success under some admissible completion per agent, and a robust variant (PAP$^{\forall }_{*_{D}}$), which requires success under all admissible completions. This distinction captures a fundamental trade-off in multi-agent coordination: optimism assumes favourable conditions, while robustness hedges against all contingencies. Our first contribution is a tight complexity classification revealing a precise quantifier-complexity correspondence: PAP$^{\exists }_{*_{D}}$ is $\varSigma _{2}^{\rm P}$-complete, while PAP$^{\forall }_{*_{D}}$ is $\varSigma _{3}^{\rm P}$-complete under extensional completion sets. The one-level gap confirms that robustness costs exactly one quantifier alternation in the polynomial hierarchy. The upper bounds follow from a small-announcement normal form—showing that effective coordination messages have bounded complexity—and NP-decidability of the distance-threshold predicate $\mathsf{Dist}_{\le }$. Second, we develop a parameterized tractability landscape that identifies when and why announcement synthesis becomes feasible despite worst-case intractability. We establish FPT algorithms parameterized by vocabulary size $k$ and announcement width $t$; FPT results for bounded completion-set sizes; and FPT in structural parameters (treewidth, backdoor size) via dynamic programming. The bounded-change variant is FPT in the $\ell _{1}$-budget $D=\sum _{i} d_{i}$. Five polynomial-time kernelization rules enable effective preprocessing. Conditional lower bounds under ETH and SETH identify unavoidable exponential dependencies. Finally, we discuss how alternative distance aggregations (average, maximum, Hausdorff) affect computational complexity, showing that our minimum-based framework provides the foundational ‘base case’ upon which more complex variants can build.