Abstract
Belief revision in artificial intelligence often faces a conflict between the rationality of the AGM postulates and the computational efficiency of restricted logical fragments. This paper investigates "Horn-to-Horn" belief revision, providing a complete characterization and a polynomial-time algorithm for determining when a successful belief contraction (a "complement") exists within the Horn fragment. Experimental results demonstrate that as knowledge bases grow, the likelihood of finding a valid Horn complement increases, suggesting the practical feasibility of this approach.
Introduction
In AI, agents must update their knowledge bases (KBs) to incorporate new information while maintaining consistency. The standard framework for this, the AGM postulates, assumes full propositional logic. However, full propositional logic is computationally expensive (NP-hard). To achieve tractability, many systems use Horn formulas, which allow for polynomial-time reasoning.
The challenge is that Horn logic is not closed under standard AGM belief revision. Removing a belief from a Horn KB might result in a non-Horn KB if one strictly follows the postulates. This research addresses the fundamental question: Under what specific conditions can we remove a belief from a Horn KB and still get a Horn KB back?
Methodology: The "Body-Building" Approach
The authors introduce a novel operation called body-building ($\hat{\phi}$) to characterize revisability. For any Horn formula $\phi$, $\hat{\phi}$ is constructed by expanding the body (the "if" part) of each clause with variables from its closure.
This construction serves as a "litmus test": a belief $\psi$ can be successfully removed from $\phi$ (leaving a Horn "complement") if and only if the body-built formula $\hat{\phi}$ does not imply $\psi$. Essentially, $\hat{\phi}$ represents the most specific version of the knowledge base. If even this version implies the belief to be deleted, a Horn-compliant contraction is impossible. The authors provide a polynomial-time algorithm to check this condition and construct the complement when it exists.
Experimental Evaluation
To assess the practical frequency of Horn-to-Horn revision, the authors conducted experiments using randomly generated Horn formulas. They varied parameters such as the number of variables ($n$), the number of clauses ($m$), and the fraction of definite clauses ($p$).
As shown in Figure 2, the percentage of beliefs that cannot be revised (those implied by the body-built formula $\hat{\phi}$) initially peaks but then decreases as the number of clauses increases. For a knowledge base with 50 clauses and 12 variables, approximately 75% of beliefs were found to have valid Horn complements.
Furthermore, Figure 1 illustrates that the fraction of definite clauses in the KB significantly impacts revisability. As the KB becomes more "definite" (containing fewer purely negative clauses), the percentage of non-revisable beliefs increases.
Key Insights and Discussion
The "body-building" intuition provides a deep semantic link between formula structure and revision possibility. The models of $\hat{\phi}$ are exactly the "singleton Horn extensions" of the original KB. This work identifies the exact boundary where computational efficiency (Horn logic) and logical rationality (AGM postulates) can coexist.
However, limitations remain. Repeated revisions might lead to a linear increase in formula size, and it is unclear if this is avoidable. When a complement does not exist, agents may need to use approximations that sacrifice some AGM postulates to maintain efficiency. Future work aims to integrate these rational update mechanisms with machine learning algorithms that induce Horn formulas from data.
Conclusion
This paper bridges the gap between theoretical belief revision and practical AI by characterizing the conditions for Horn-to-Horn contraction. The discovery of a polynomial-time algorithm and the high frequency of revisable beliefs in random KBs offer a promising path toward efficient, rational knowledge management systems.
Summary updated