Belief revision in Horn theories (Q2512985)

In recent years a number of researchers have worked on the problem of adapting the AGM account of belief change to the restricted context of Horn theories. Although valuable results have been obtained, the enterprise has faced difficulties arising from the limited expressive power of Horn formulae. The link between contraction and revision, which in the classical context is provided by the Levi identity, breaks down as does the correspondence between existing semantics and postulates for revision. In terms of the Katsuno-Mendelzon semantics, we can say that there are some total pre-orderings of worlds whose induced revision operations for Horn theories fail the natural counterparts of the AGM `supplementary postulates' and, conversely, some operations that satisfy those postulates are no longer representable by those orderings. The paper under review solves these difficulties (for revision, in the finite propositional case) by refining both the semantics and the syntax. On the semantic side, it imposes on total pre-orders a constraint of `Horn compliance'; on the syntactic side, it adds an `acyclicity' condition to the natural counterparts of the AGM postulates. The central result of the paper is that with these adjustments in place we can obtain a representation theorem linking the syntactic and semantic dimensions. Further results establish the consistency of this approach with the Darwiche-Pearl postulates for iterated revision, and again with Parikh's relevance criterion (but not with both simultaneously, as they are known to conflict with each other). Finally, the paper investigates certain specific computable Horn revision operations. While those of Dalal and of Satoh, designed for the classical setting, cannot be applied directly in the Horn context, nevertheless they provide the authors with a guiding intuition for constructing their own specific operations of polynomial time complexity. Reviewer's comment: The paper succeeds in bringing together many disparate strands of earlier research to create a solid platform where syntax and semantics are mutually supportive. It seems likely that future work on belief change in Horn theories will take this platform as a starting point.