TITLE:
Applying DNA Computation to Error Detection Problem in Rule-Based Systems
AUTHORS:
Behrouz Madahian, Amin Salighehdar, Reza Amini
KEYWORDS:
DNA Computing, Rule-Based Systems, Rule Verification, Structural Errors
JOURNAL NAME:
Journal of Intelligent Learning Systems and Applications,
Vol.7 No.1,
February
13,
2015
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.