A token-flow paradigm for verification of rule-based expert systems

This paper presents a novel approach to the verification of rule-based systems (RBSs). A graph structure, called the rule-dependency graph (RDG), is introduced to describe the dependency relationship among the rules of an RBS, in which each type of improper knowledge forms a specific topological structure. Knowledge verification is then performed by searching for such topological structures through a token-flow paradigm. An algorithm is provided, which automatically generates a minimally sufficient set of literals as test tokens in the detection procedure. The proposed scheme can be applied to rules of non-Horn clause form in both propositional and first-order logic, and restrictions imposed by other graph-based approaches can be avoided. Furthermore, explicit and potential anomalies of RBSs can be correctly found, and efficient run-time validation is made possible.