Generating Minimum-Cost Fault-Free Rule Bases Using Minimum Spanning Trees

Abstract

This paper presents a new approach/algorithm for generating minimum-cost fault-free rule bases, which have no redundancy, circularity, inconsistency, contradiction/conflict and unreachability. The approach makes use of minimum spanning trees to check a rule base for different kinds of faults. The rule base is represented using a directed weighted graph. The algorithm devises a spanning tree/forest of the underlying directed graph by treating the directed graph as an undirected graph, and checks for various faults and properti es. The algorithm devises a new rule base (which is a subset of the original rule base) that is equivalent, in terms of its reasoning capabilities, to the original rule base, with the properties that the new rule base is free from redundancy and circularity and has the minimum cost. It also determines the set of rules that cause redundancy and circularity faults. After determining the new rule base, checking for the remaining faults, namely inconsistency, contradiction, and unreachability, can be performed in a straightforward manner using the generated structures.