Horn knowledge bases are widely used in many applications. This paper is
concerned with the optimal compression of propositional Horn production
rule bases - one of the most important knowledge bases used in practice.
The problem of knowledge compression is interpreted as a problem of
Boolean function minimization. It was proved in [14] that the minimization
of Horn functions, i.e. Boolean functions associated to Horn knowledge
bases, is NP-complete.
This paper deals with the minimization of quasi-acyclic Horn functions,
the class of which properly includes the two practically significant
classes of quadratic and of acyclic functions. A procedure is developed
for recognizing in quadratic time the quasi-acyclicity of a function
given by a Horn CNF, and a graph-based algorithm is proposed for the
quadratic time minimization of quasi-acyclic Horn functions.
DIMACS Home Page