Introduction
In the study of artificial intelligence and formal logic, two fields have long been viewed as two sides of the same coin: Belief Revision and Non-Monotonic Reasoning (NMR). Belief Revision focuses on how an agent updates its knowledge base $K$ when presented with new information $x$. Non-monotonic reasoning describes the process of drawing plausible conclusions $y$ from evidence $x$, given a background of existing beliefs $K$, where new information might force the retraction of previous inferences.
Traditionally, the relationship between these two domains is governed by the AGM paradigm, a set of postulates that define rational belief change. This "bridge" between revision and inference relies heavily on the assumption of compactness—the property that if a set of premises entails a conclusion, some finite subset of those premises must also entail it. However, many critical logics in computer science, such as the Temporal Logics used in formal verification and AI planning, are non-compact. This paper investigates whether the fundamental symmetry between belief revision and non-monotonic reasoning holds when the safety net of compactness is removed.
The Challenge of Non-Compactness
In classical, compact logics, adding information never invalidates previous conclusions (monotonicity). Human reasoning, however, is non-monotonic. For example, if we learn that Tweety is a bird, we might infer he flies; if we later learn Tweety is a penguin, we retract that inference.
While the AGM postulates (K1–K8) provide a gold standard for rational revision, they were developed with compact logics in mind. The authors demonstrate that in non-compact settings, the standard axioms for non-monotonic inference (N1–N9) are no longer sufficient to guarantee AGM-rational behavior. Specifically, the "return trip" from an inference system back to a belief revision operator breaks down. An inference system might satisfy all standard rules yet still lead to "irrational" belief changes, such as the arbitrary loss or gain of information when presented with empty evidence.
Methodology
The authors employ a purely theoretical approach, utilizing formal logical proofs to analyze the interaction between AGM postulates and non-monotonic axioms. Their method involves:
- Counter-example Construction: Identifying scenarios where standard axioms fail to produce rational belief revision in non-compact environments.
- Axiomatic Extension: Proposing new logical constraints to address these failures.
- Representation Theorems: Proving that their augmented set of axioms is exactly equivalent to the AGM postulates, even in the absence of compactness.
Key Insights: The New Guardrail Axioms
The research reveals that in non-compact logics, standard axioms like "Right Weakening" and "And" fail to ensure logical closure. To repair the link between revision and inference, the authors introduce three critical new conditions:
- $Closure_{NM}$: This axiom explicitly requires that the set of non-monotonic consequences is logically closed. In compact logics, this is a byproduct of other rules, but in non-compact logics, it must be enforced.
- Keeper: This ensures that if an agent infers something from a tautology (empty evidence), that information must have already existed in the original belief set. This prevents the "inappropriate acquisition" of beliefs.
- Rooting: The converse of the Keeper axiom, Rooting ensures that an agent does not "forget" existing beliefs when presented with empty evidence.
Theoretical Results
The paper's primary contribution is the restoration of the representation theorem for non-compact logics. Key findings include:
- Theorem 2: Demonstrates that standard axioms are insufficient for logical closure in non-compact settings.
- Theorems 5 & 6: Show that a system can satisfy all traditional NMR axioms while still violating basic AGM rationality, specifically the "Inclusion" and "Preservation" postulates.
- The Representation Theorem (Corollaries 3 & 5): The authors prove that a belief change operator is AGM-rational if and only if its corresponding inference relation satisfies the standard axioms plus the new $Closure_{NM}$, Keeper, and Rooting axioms.
Conclusion and Future Work
By identifying and filling the gaps left by the absence of compactness, this work provides a generalized framework for belief revision that is applicable to complex, non-compact languages like Linear Temporal Logic (LTL) and Computation Tree Logic (CTL). These logics are essential for the formal verification and "automatic repair" of software specifications.
While this paper establishes the necessary theoretical postulates, future research is required to explore specific algorithmic constructions—such as "partial meet" or "kernel" revision—within these non-compact systems. This will be a vital step toward implementing robust belief revision in practical AI and formal verification tools.
Summary updated