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