USING DIRECTED HYPERGRAPHS TO VERIFY RULE-BASED EXPERT-SYSTEMS

Rule-based representation techniques have become popular for storage a nd manipulation of domain knowledge in expert systems. It is important that systems using such a representation are verified for accuracy be fore implementation. In recent years, graphical techniques have been f ound to provide a good framework for the detection of errors that may appear in a rule base [1], [16], [17], [19], [23]. In this work we pre sent a graphical representation scheme that: 1) captures complex depen dencies across clauses in a rule base in a compact yet intuitively cle ar manner and 2) is easily automated to detect structural errors in a rigorous fashion. Our technique uses a directed hypergraph to accurate ly detect the different types bf structural errors that appear iri a r ule base. The technique allows rules to be represented in a manner tha t clearly identifies complex dependencies across compound clauses. Sub sequently, the verification procedure can detect errors in an accurate fashion by using simple operations on the adjacency matrix of the dir ected hypergraph. The technique is shown to have a computational compl exity that is comparable to that of other graphical techniques. The gr aphical representation coupled with the associated matrix operations i llustrate how directed hypergraphs are a very appropriate representati on technique for the verification task.