DIMACS TR: 93-37
Quasi-Acyclic Propositional Horn Knowledge Bases:
Optimal Compression
Authors: Peter L. Hammer and Alexander Kogan
ABSTRACT
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.
Paper available at:
ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1993/93-37.ps
DIMACS Home Page