When a knowledge base receives new information that contradicts its existing beliefs, or when an outdated fact must be removed, the system must perform a belief change operation. The gold standard for modeling this process is the classical AGM framework, which defines how an agent can rationally revise or contract its beliefs. However, the AGM framework was originally built on a major assumption: that the underlying language is a highly expressive classical logic containing all standard boolean connectives, such as conjunction ($\land$), disjunction ($\lor$), and negation ($\neg$).
In modern artificial intelligence, we frequently use simpler, more computationally efficient languages—such as Horn logic, Description Logics (DLs), or lightweight fragments of first-order logic—to manage massive ontologies and databases. As Qi et al. point out, adapting belief change to these description logics introduces significant theoretical hurdles. Because these languages deliberately restrict or omit connectives like negation and disjunction to keep reasoning tractable, the classical machinery of belief change breaks down.
The Disjunction Bottleneck
To understand why missing connectives break belief contraction, we must look at how classical systems decide which beliefs to discard. When removing a belief $\alpha$ from a knowledge base, we want to retain as much valuable information as possible. Classical AGM contraction often relies on a preference ordering over formulas known as epistemic entrenchment.
In standard propositional logic, if you want to choose between keeping belief $\beta$ or belief $\gamma$ when forced to contract $\alpha$, the system evaluates the epistemic entrenchment of the disjunctions $\alpha \lor \beta$ and $\alpha \lor \gamma$. The disjunction acts as a mathematical bridge, allowing the system to compare the relative cognitive weight of independent beliefs.
But what happens if your logical language cannot express "OR"? In Horn logic or lightweight description logics like DL-Lite, a formula like $\alpha \lor \beta$ is syntactically invalid. Without the ability to form disjunctions, standard epistemic entrenchment operators cannot be formulated. As observed by Booth et al. in the context of propositional Horn theories, standard contraction methods become far too rigid, often forcing the system to drop large clusters of valid beliefs simply because it lacks the expressive syntax to surgically isolate and remove just one.
Bypassing Disjunction via Logical Proxies
The core insight that makes belief change possible in restricted fragments is that we can find implicit structural substitutes for disjunction within the logic itself. We do not need an explicit $\lor$ operator if we can find other formulas that mimic its behavior.
Wang et al. demonstrated that belief contraction can be generalized to any logic supporting conjunction by identifying a set of formulas that logically entail the missing disjunction. Instead of evaluating $\alpha \lor \beta$ directly, the framework identifies a proxy set of native formulas that capture the same logical relationship. This allows for principled, syntax-independent belief retraction across diverse, weak fragments.
Classical AGM:
[ Evaluate α ∨ β ] --> Requires explicit disjunction operator
Restricted Fragments (Wang et al.):
[ Find native formulas that logically entail (α ∨ β) ] --> Bypasses disjunction operator
Applying this strategy to description logics, Wang et al. showed how to eliminate problematic axioms from DL-Lite ontologies. By replacing disjunction-dependent operators with structural relationships between existing axioms, the authors designed a rational contraction function that operates entirely within the constraints of the lightweight logic profile. This ensures that existing reasoning engines can handle belief updates natively without requiring non-standard extensions to the language. To scale this to broader subsets of first-order logic, Wang et al. introduced "FC approximations" and "epistemic cuts," proving that the core mathematical principles of contraction are fundamentally independent of specific logical connectives.
Postulates and Varied Revision Attitudes
To prove that these modified contraction functions behave predictably, researchers evaluate them against formal rationality postulates. For example, a contraction operator must satisfy success (ensuring the target axiom is actually removed) and inclusion (ensuring the operation does not randomly introduce entirely new information). Crucially, Wang et al. emphasize syntax independence: if two axioms are logically equivalent, removing either one must yield the exact same updated knowledge base, preventing the internal phrasing of an ontology from distorting its evolution.
With a solid foundation for contraction established, the framework can be expanded to capture different behavioral profiles and types of knowledge:
- Shielded Contraction: In many practical applications, certain core beliefs should be completely protected from deletion. Garapa et al. formalized this by mapping out "shielded base contractions," creating a hierarchical structure of operators that define exactly which beliefs an agent can or cannot safely retract.
- Varying Revision Attitudes: Classical belief change is highly conservative, fiercely protecting existing beliefs when incorporating new, consistent data. Haret et al. introduced relaxed axioms that allow agents to exhibit a wider spectrum of attitudes, ranging from strict conservatism to a willingness to discard initial beliefs more readily in response to environmental changes.
- Prioritized and Uncertain Information: Real-world knowledge bases often contain weighted or uncertain data. Qi et al. extended these concepts to possibilistic logic, designing conflict-based revision operators that allow an entire prioritized knowledge base to be revised by another, while still satisfying formal logical standards like the Katsuno-Mendelzon postulates.
Ultimately, this research direction demonstrates that the rationality of belief change does not depend on the complexity of the language. By substituting missing connectives with structural proxies, autonomous agents can maintain consistent, evolving, and predictable knowledge bases within the tight computational boundaries of lightweight logical fragments.
Key Foundational Work
Next Steps in Propositional Horn Contraction (2009) — contributed 1 concept elements to this direction.
A Survey of Revision Approaches in Description Logics (2008) — contributed 1 concept elements to this direction.