Abstract
Classical belief revision frameworks often treat new information as absolute truth, failing to account for nuanced meta-data such as source reliability. Hans Rott's Bounded Revision (BR) addresses this by introducing a reference sentence to limit the depth of revision. This paper provides a formal implementation of BR, proving its equivalence to lexicographic revision via a "core" formula and demonstrating its compatibility with ranking functions and c-revisions. This bridge between abstract theory and practical algorithms enables the integration of bounded trust into automated reasoning systems.
Introduction
In the Alchourrón, Gärdenfors, and Makinson (AGM) framework, belief revision is typically modeled as an agent accepting new information $\beta$ with the highest possible priority. However, real-world reasoning is rarely so binary. Information often comes with context—a source's expertise or the reliability of a sensor. For example, if a tour guide provides a fact about George Washington, you might accept it only as far as you trust their expertise on history, without allowing it to overrule your core beliefs.
To model this, Hans Rott introduced Bounded Revision (BR). In BR, an agent receives an input $\beta$ alongside a reference sentence $\alpha$. The agent's goal is to "Accept $\beta$ as far as $\alpha$ and just a little further." While intuitively strong, the formal implementation of BR remained computationally difficult until this recent work presented at AAAI-23.
Bounded Revision and Plausibility Rankings
The semantic foundation of belief revision lies in Total Preorders (TPOs) over possible worlds, representing an agent's plausibility ranking. In standard revision, all worlds satisfying the new information are promoted to the top. In Bounded Revision, this promotion is constrained by the reference point.
As illustrated in Figure 3, the BR operator $*_a b$ rearranges the worlds such that the input $b$ is integrated, but its impact is modulated by the bound $a$. This prevents the "blunt" promotion seen in standard lexicographic revision, where all $b$-worlds would otherwise be moved to the highest plausibility level regardless of their prior status.
Theoretical Foundations: The Core Formula
The most significant theoretical contribution of this paper is the identification of a "core" formula, $\phi_{\alpha,\beta}$. This formula encapsulates the meta-information provided by the reference sentence $\alpha$ directly into an object-level formula.
The authors prove a major representation theorem: Bounded Revision by $\beta$ with respect to $\alpha$ is mathematically equivalent to a standard lexicographic revision using this core formula $\phi_{\alpha,\beta}$. This reduction simplifies a complex "two-dimensional" revision problem into a standard one-dimensional one. Furthermore, the authors propose three semantic postulates (BR1–BR3) that characterize how an agent's plausibility ranking should change, ensuring the method behaves rationally over multiple updates and satisfies the Darwiche-Pearl (DP) postulates for iterated revision.
Implementation via Ranking Functions
To move from qualitative logic to practical tools, the authors utilize Ordinal Conditional Functions (OCFs), or ranking functions. They demonstrate that BR can be perfectly mirrored using "minimal c-revisions"—a specific type of update that handles conditional information.
Figure 6 shows how the framework handles various scenarios, such as revisions with different bounds and inputs (e.g., $*_b c$ and $*_a \bar{d}$). By showing that BR fits within the c-revision framework, the authors ensure compatibility with existing Java-based belief revision tools. This means developers can now implement "bounded" trust without needing to build entirely new revision engines from scratch.
Conclusion
This paper successfully bridges the gap between the abstract theory of Bounded Revision and practical, implementable algorithms. By reducing BR to lexicographic revision and providing a path through ranking functions, the authors have provided a robust framework for AI agents to handle information with varying degrees of trust. Future work will explore the long-term behavior of sequences of bounded revisions and the extension of these methods to more expressive first-order logics.
Summary updated