Non-characterizability of belief revision: an application of finite model theory
This addresses a foundational issue in formal logic and AI for researchers in belief revision, but it is incremental as it builds on existing frameworks to prove a specific non-characterizability result.
The paper tackles the problem of characterizing belief revision operators using postulates, showing that for a class defined via partial orders, characterizability implies a definability property in monadic second-order logic, and provides an example of a non-characterizable class, marking the first such result in belief revision.
A formal framework is given for the characterizability of a class of belief revision operators, defined using minimization over a class of partial preorders, by postulates. It is shown that for partial orders characterizability implies a definability property of the class of partial orders in monadic second-order logic. Based on a non-definability result for a class of partial orders, an example is given of a non-characterizable class of revision operators. This appears to be the first non-characterizability result in belief revision.