DIMACS TR: 93-06
Optimal Compression of Propositional Horn Knowledge Bases:
Complexity and Approximation
Authors: Peter L. Hammer and Alexander Kogan
ABSTRACT
Horn formulae play a prominent role in artificial intelligence and logic
programming. In this paper we investigate the problem of optimal compression
of propositional Horn production rule knowledge bases. The standard approach
to this problem, consisting in the removal of redundant rules from a knowledge
base, leads to an ``irredundant'' but not necessarily optimal knowledge base.
We prove here that the number of rules in any irredundant Horn knowledge base
involving n propositional variables is at most n - 1 times the minimum
possible number of rules. In order to formalize the optimal compression
problem, we define a Boolean function of a knowledge base as being the
function whose set of true points is the set of models of the knowledge base.
In this way the optimal compression of production rule knowledge bases becomes
a problem of Boolean function minimization. In this paper we prove that the
minimization of Horn functions (i.e. Boolean functions associated to Horn
knowledge bases) is NP-complete.
Paper available at:
ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1993/93-06.ps
DIMACS Home Page