Rational Belief Contraction for Lightweight Logics

You are reading version 1 of this direction, frozen 2026-10-04. The latest version is version 2.

Version 1 of 226 papers50 conceptsfrozen 2026-10-04

In classical artificial intelligence, an agent’s knowledge is rarely static. When new information arrives that contradicts existing beliefs, or when a specific fact must be "forgotten" to maintain privacy or resolve an inconsistency, the agent must perform belief change.

For decades, the "gold standard" for this process has been the AGM framework—named after Alchourrón, Gärdenfors, and Makinson—which defines a set of rationality postulates for how an agent should retract information (contraction) or incorporate new facts (revision) while ensuring "minimal change."

However, a significant problem has emerged: the AGM framework was designed for powerful, expressive logics (like propositional logic) that include operators for negation ($\neg$) and disjunction ($\lor$). Modern AI applications, such as the Semantic Web and large-scale ontologies, instead rely on "lightweight" logics like Description Logics (DLs) and Horn logic. These fragments are intentionally restricted to ensure computational efficiency, but they lack the very operators the AGM framework requires to function.

The Expressivity Gap

The core of the challenge, as identified by Hirofumi Katsuno and Alberto O. Mendelzon in A Unified View of Propositional Knowledge Base Updates, is that removing information is not just about deleting a line of code. It requires identifying the logical dependencies of that information.

In a logic with disjunction, if you want to retract the belief $A$, you can often replace it with $A \lor B$. But in lightweight logics like $\mathcal{EL}$ or DL-Lite, disjunction is forbidden. As Zhe Wang, Zhiqiang Zhuang, and Kewen Wang point out in Rational Elimination of DL-Lite TBox Axioms, without these operators, we cannot natively support standard rational change operators. We are left with a "gap" that the logic cannot express.

Why the Recovery Postulate Fails

The most controversial of the AGM rules is the Recovery Postulate. It states that if you remove a belief and then immediately add it back, you should return to your original state of knowledge.

In expressive logics, this is a cornerstone of "minimal change." But in restricted logics, it is often mathematically impossible to satisfy. Giorgos Flouris and colleagues argued in Inconsistencies, Negations and Changes in Ontologies that because these logics cannot express the "negation" of an axiom, they cannot precisely isolate what needs to be removed.

Consider a logic that can say "All Humans are Mortals" but cannot say "Not all Humans are Mortals." If you try to retract the idea that humans are mortals, the logic might be forced to delete more information than necessary because it lacks the surgical tools to cut out just that one specific implication. As Zhiqiang Zhuang demonstrates in Entrenchment-Based Horn Contraction, this makes the contraction process inherently "lossy," rendering the recovery postulate unattainable.

Redefining Rationality through Relevance

If the recovery postulate is broken, how do we ensure an update is still "rational"? Researchers have proposed replacing it with new principles:

  1. Relevance and Fullness: Instead of worrying about returning to the original state, we ensure that only information related to the retracted belief is removed. Maurice Pagnucco and Zhiqiang Zhuang suggest using logical difference—the set of axioms entailed by one theory but not another—as a metric for minimal change in Belief Contraction in the Description Logic EL.
  2. Relevance-Based Change: In Language Splitting and Relevance-Based Belief Change in Horn Logic, Dongmo Zhang and others show that by focusing on the specific "atoms" or variables involved, we can perform updates that are both logically sound and computationally efficient.
  3. Relaxation: Marc Aiguier and Isabelle Bloch propose a "relaxation" approach in Belief revision, minimal change and relaxation. Rather than deleting a belief entirely, the system gradually "loosens" the constraints of the old belief until it no longer conflicts with the new information.

From Syntax to Semantics

To make these ideas practical, the research has shifted from manipulating the text of the rules (syntax) to manipulating the underlying models (semantics).

A breakthrough in this area is the use of Type Semantics. In DL-Lite Contraction and Revision, Zhe Wang and Guilin Qi introduce a finite, succinct way to represent the infinite models of Description Logics. This allows for polynomial-time algorithms that can "forget" variables or retract axioms by identifying the minimal set of "types" (possible states of an object) that must be modified.

Similarly, in the realm of Logic Programming, Kewen Wang and Abdul Sattar 0001 developed a theory of forgetting in A Theory of Forgetting in Logic Programming. Their approach ensures that logically equivalent programs result in the same outcome after forgetting, a property called "strong persistence" that is vital for maintaining the integrity of knowledge bases.

The Path Forward: Generalizing Change

The ultimate goal of this research direction is a unified theory that works across any logic fragment. James P. Delgrande and Zhe Wang have made significant strides in Extending AGM Contraction to Arbitrary Logics and A Generalisation of AGM Contraction and Revision to Fragments of First-Order Logic.

By using approximations—finding the closest representable formula within a restricted logic to a non-representable one—they have shown that the core principles of rational belief change are not tied to specific operators like negation or disjunction. Instead, they are fundamental properties of how information and dependence interact in any structured system of thought.

Papers in this version

History & citationVersion 2 · 2026-10-04

Current · Permanent link

  1. Version 2 (latest) · 2026-10-04 · 13 papers
  2. Version 1 · 2026-10-04 · 26 papers
Cite this direction

Latest version (a living page):

@misc{lacuna_recovery_postulate_incompatibility_19738f5d,
  title = {recovery postulate incompatibility},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/recovery-postulate-incompatibility/rdr_19738f5dab2843989290bfe1f825b75d},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-19},
}

This exact version (version 1, frozen text):

@misc{lacuna_rational_belief_contraction_for_lightwei_19738f5d_v1,
  title = {Rational Belief Contraction for Lightweight Logics},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/rational-belief-contraction-for-lightweight-logics/rdr_19738f5dab2843989290bfe1f825b75d/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-19},
}