Fault Detection in Dynamic Rule Bases Using Spanning Trees and Disjoint Sets

Nabil Arman

Palestine Polytechnic University, Palestine 

Abstract: Many fault detection techniques/algorithms for detecting faults in rule bases have appeared in the literature. These techniques assume that the rule base is static. This paper presents a new approach/algorithm for detecting faults in dynamic rule bases, where rules may be added/deleted in response to certain events happening in the system being controlled by the rule base. This is performed by maintaining a set of structures, where new rules can be added to the dynamic rule base without the need to rebuild the structures that represent the rule base. The approach makes use of spanning trees and disjoint sets to check a dynamic rule base for different kinds of faults. The algorithm devises a tree/forest of the underlying directed graph by treating the directed graph as an undirected graph, and then checks for various faults and properties. The algorithm devises a new rule base (which is a subset of the current rule base) that is equivalent, in terms of its reasoning capabilities, to the current rule base, with the properties that the new rule base is fault free. This is performed as rules are being added to the dynamic rule base one at a time.  

 Keywords: Dynamic rule bases, rule base faults, spanning trees. 

Received October 1, 2005; accepted March 15, 2006