Applying DNA Computation to Error Detection Problem in Rule-Based Systems

Abstract

As rule-based systems (RBS) technology gains wider acceptance, the need to create and maintain large knowledge bases will assume greater importance. Demonstrating a rule base to be free from error remains one of the obstacles to the adoption of this technology. In the past several years, a vast body of research has been carried out in developing various graphical techniques such as utilizing Petri Nets to analyze structural errors in rule-based systems, which utilize propositional logic. Four typical errors in rule-based systems are redundancy, circularity, incompleteness, and inconsistency. Recently, a DNA-based computing approach to detect these errors has been proposed. That paper presents algorithms which are able to detect structural errors just for special cases. For a rule base, which contains multiple starting nodes and goal nodes, structural errors are not removed correctly by utilizing the algorithms proposed in that paper and algorithms lack generality. In this study algorithms mainly based on Adleman’s operations, which are able to detect structural errors, in any form that they may arise in rule base, are presented. The potential of applying our algorithm is auspicious giving the operational time complexity of O(n*(Max{q, K, z})), in which n is the number of fact clauses; q is the number of rules in the longest inference chain; K is the number of tubes containing antecedents which are comprised of distinct number of starting nodes; and z denotes the maximum number of distinct antecedents comprised of the same number of starting nodes.