Belief Revision, Decomposition and Horn Formulas

Speaker: Professor Robert Sloan, University of Illinois at Chicago

Venue: CB 201


Horn-to-Horn belief revision asks for the revision of a Horn knowledge base such that the revised knowledge base is also Horn. Horn knowledge bases are important whenever one is concerned with efficiency of computing inferences, of knowledge acquisition, etc. Horn-to-Horn belief revision could be of interest, in particular, as a component of any efficient system requiring large commonsense knowledge bases that may need revisions because, for example, new contradictory information is acquired.

Recent results on belief revision for general logics show that the existence of a belief contraction operator satisfying the generalized AGM rationality postulates (which we will discuss for those unfamiliar with them) is equivalent to the existence of a complement. Here we provide a first step towards efficient Horn-to-Horn belief revision, by characterizing the existence of a complement of a Horn consequence of a Horn knowledge base. A complement exists if and only if the Horn consequence is not the consequence of a modified knowledge base obtained from the original by an operation called body building. This characterization leads to the efficient construction of a complement whenever it exists.

(Joint work with Marina Langlois, Balazs Szorenyi, and Gyorgy Turan)

Host: Professor J. Goldsmith.

(Speaker's personal page)