Essential and redundant rules in Horn knowledge bases

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. The identification of essential rules indicates 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. 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. The paper provides combinatorial characterizations and computational recognition procedures of essentiality and redundancy of prime rules of Horn knowledge bases