Introduction
In the field of Artificial Intelligence, belief revision is the study of how an agent should update its knowledge base when it encounters new, potentially conflicting information. The gold standard for this is the AGM framework, which defines "rational" revision through a set of axioms or postulates. Typically, researchers start with postulates and then identify mathematical structures—such as total preorders of "possible worlds"—that satisfy them. This paper investigates the inverse problem: given a class of revision operators defined by specific geometric or computational constraints, is there always a finite set of postulates that perfectly captures that class? This "characterizability" problem identifies the boundary between revision models that can be axiomatized and those that cannot.
Theoretical Framework
The authors base their framework on the work of Katsuno and Mendelzon (KM), where revision is viewed as selecting the "minimal" models of a new formula based on a faithful partial order (poset). The core of the paper is the mapping between classes of relations (posets) and the revision operators they induce.
A central technical contribution is the definition of a translation $\tau$ that turns standard belief revision postulates into sentences in a specific logic. This allows the researchers to treat characterizability as a problem of logical definability.
The Logic of Minimization
The paper's primary insight is that characterizability is not a matter of standard First-Order Logic. Because revision operators inherently look for minimal elements, the postulates are actually making claims about the "min-sets" of the structure. The authors prove that a class of revision operators is characterizable if and only if its underlying class of posets is definable within $\forall MSO_{min}$, a fragment of Monadic Second-Order logic equipped with a minimization operator.
To prove that certain classes cannot be characterized, they adapt the Ehrenfeucht-Fraïssé game into a new variant called the Katsuno-Mendelzon (KM) game. If a "Duplicator" player has a winning strategy in this game between two structures, it proves that the logic cannot distinguish between them, and thus the class is not characterizable.
Key Results
The study demonstrates a surprising gap between intuitive model descriptions and their axiomatizability. While some structures are easily characterized, others that seem simple are impossible to capture with finite postulates.
- Characterizable Classes: These include posets with bounded height (where rankings aren't too deep), posets with bounded width, and total orders (the classic AGM case).
- Non-Characterizable Classes:
- Width $\ge 2$: The class of all revision operators that are not total orders cannot be characterized by a finite set of postulates.
- Connectedness: One cannot write a finite set of postulates that captures the requirement that the underlying preference model is "connected."
Conclusion
By establishing an equivalence between characterizability and $\forall MSO_{min}$-definability, this research provides a rigorous toolset for evaluating belief revision models. It highlights that the "minimal-element-only" lens of belief revision postulates is inherently limited, unable to capture certain first-order properties like connectedness. Future work aims to extend this framework to iterated revision and belief contraction, further mapping the landscape of what can—and cannot—be formally axiomatized in intelligent systems.
Summary updated