## 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