## DIMACS TR: 94-42

## Essential and Redundant Rules in Horn Knowledge Bases

### Authors: Peter L. Hammer, Alexander Kogan

**
ABSTRACT
**

A production rule of a knowledge base is called essential if it is
present in any prime knowledge base which is logically equivalent to the
given one. Identification of essential rules constitutes a crucial part of
the structural analysis of any knowledge base. It specifies the degree of
freedom we have in constructing logically equivalent transformations of the
base, by specifying the set of rules which must remain in place, and
implicitly showing which rules could be replaced by other ones.
A prime rule is called redundant if it is not present in any irredundant
prime knowledge base which is logically equivalent to the given one.
Redundant rules can be viewed as the ``least important'' prime rules of a
knowledge base. The recognition of redundancy of a particular prime rule in
a knowledge base will eliminate such rule from consideration in any future
simplifications of the knowledge base.

This paper provides combinatorial characterization of essential and redundant
rules of propositional Horn knowledge bases, and develops, whenever possible,
efficient computational procedures for recognizing essentiality and redundancy
of prime rules of Horn knowledge bases.

Paper available at:
ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1994/94-42.ps

DIMACS Home Page