Compilability and Compact Representations of Revision of Horn Knowledge Bases

Paolo Liberatore

ACM Transactions on Computational Logic

Several methods have been proposed as an attempt to deal with dynamically-changing scenarios. From a computational point of view, different formalisms have different computational properties. In this paper we consider knowledge bases represented as sets of Horn clauses. The importance of this case is twofold: first, inference is polynomial, thus tractable; second, Horn clauses represent causal relations between facts, thus they are of great practical importance, although not all propositional knowledge bases can be represented in Horn form. The complexity of Horn revision is still high, and in some cases coincides with the complexity of the general (non-Horn) case. We analyze the complexity of belief revision from the point of view of the compilation: we study the possibility of reducing the complexity by allowing a (possibly expensive) preprocessing of part of the input of the problem. Extending the work by Cadoli et al. [1999], we consider the problem of compact representation of revision in the Horn case, that is, given a knowledge base T and an update P (both represented by Horn clauses) decide whether T *P, the result of the revision, can be represented with a propositional formula whose size is polynomial in the size of T and P. We give this representation for all formalisms for which it exists, and we show that the existence of a compact representation is related to the possibility of decreasing the complexity of a formalism via a preprocessing.


 @article{libe-00-b,
 title = {Compilability and Compact Representations of Revision of
 Horn Knowledge Bases},
 year = {2000},
 author = {Liberatore, Paolo},
 journal = {ACM Transactions on Computational Logic},
 pages = {131--161},
 number = {1},
 volume = {1},
 }
 
HTTP download.
doi: 10.1145/343369.343391