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

Read  full  paper  at:

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.

Cite this paper

Madahian, B. , Salighehdar, A. and Amini, R. (2015) Applying DNA Computation to Error Detection Problem in Rule-Based Systems. Journal of Intelligent Learning Systems and Applications, 7, 21-36. doi: 10.4236/jilsa.2015.71003.


[1] Yeh, C.-W. and Chu, C.-P. (2008) Molecular Verification of Rule-Based Systems Based on DNA Computation. IEEE Transactions on Knowledge and Data Engineering, 20, 965-975.
[2] Jeffrey, J., Lobo, J. and Murata, T. (1996) A High-Level Petri Net for Goal-Directed Semantics of Horn Clause Logic. IEEE Transactions on Knowledge and Data Engineering, 8, 241-259.
[3] Yang, S.J.H., Tsai, J.P. and Chen, C.C. (2003) Fuzzy Rule Base Systems Verification Using High-Level Petri Nets. IEEE Transactions on Knowledge and Data Engineering, 15, 457-473.
[4] Ligeza, A. (2006) Logical Foundations for Rule-Based Systems. Springer, New York, 189-211.
[5] Tan, Z.-H. (2006) Fuzzy Metagraph and Its Combination with the Indexing Approach in Rule-Base Systems. IEEE Transactions on Knowledge and Data Engineering, 18, 829-841.
[6] He, X., Chu, W.C., Yang, H. and Yang, S.J.H. (1999) A New Approach to Verify Rule-Based Systems Using Petri Nets. The 23rd Annual International Computer Software and Applications Conference, Phoenix, 27-29 October 1999, 462-467.
[7] Nguyen, T.A. (1987) Verifying Consistency of Production Systems. 3rd IEEE Conference on Artificial Intelligence and Applications, Orlando, 4-8.
[8] Nguyen, T.A., Perkins, W.A., Laffey, T.J. and Pecora, D. (1985) Checking Expert System Knowledge Bases for Consistency and Completeness. Ninth International Joint Conferences on Artificial Intelligence, Los Angeles, August 1985, 375-378.
[9] Cragun, B.J. and Steudel, H.J. (1987) A Decision-Table-Based Processor for Checking Completeness and Consistency in Rule-Based Expert Systems. International Journal of Man-Machine Studies, 26, 633-648.
[10] Ramaswamy, M., Sarkar, S. and Chen, Y.S. (1997) Using Directed Hypergraphs to Verify Rule-Based Expert Systems. IEEE Transactions on Knowledge and Data Engineering, 9, 221-237.
[11] Nazareth, D.L. and Kennedy, M.H. (1991) Verification of Rule-Based Knowledge Using Directed Graphs. Knowledge Acquisition, 3, 339-360.
[12] Valiente, G. (1993) Verification of Knowledge Based Redundancy and Subsumption Using Graph Transformations. International Journal of Expert Systems, 6, 341-355.
[13] Nazareth, D.L. (1993) Investigating the Applicability of Petri Nets for Rule-Based System Verification. IEEE Transactions on Knowledge and Data Engineering, 4, 402-415.
[14] Agarwal, R. and Tanniru, M. (1992) A Petri Net Based Approach for Verifying the Integrity of Production Systems. International Journal of Man-Machine Studies, 36, 447-468.
[15] Wu, C.H. and Lee, S.J. (1997) Knowledge Verification with an Enhanced High-Level Petri-Net Model. IEEE Expert, 12, 73-80.
[16] Amos, M. (2004) Theoretical and Experimental DNA Computation. Springer, New York, 46-77.
[17] Feynman, R.P. and Gilbert, D. (1960) There’s Plenty of Room at the Bottom. Engineering and Science Magazine, 23, 22-36.
[18] Adleman, L.M. (1994) Molecular Computation of Solutions to Combinatorial Problems. Science, 266, 1021-1024.
[19] Breslauer, K.J., Frank, R., Blocker, H. and Marky, L.A. (1986) Predicting DNA Duplex Stability from the Base Sequence. Proceedings of the National Academy of Sciences, 83, 3746-3750.
[20] Braich, R.S., Johnson, C., Rothemund, P.W.K., Hwang, D., Chelyapov, N. and Adleman, L.M. (2001) Solution of a Satisfiability Problem on a Gel-Based DNA Computer. DNA Computing Lecture Notes in Computer Science, 2054, 27-42.
[21] Roweis, S., Winfree, E., Burgoyne, R., Chelyapov, N.V., Goodman, M.F., Rothemund, P.W.K. and Adleman, L.M. (1998) A Sticker-Based Model for DNA Computing. Journal of Computational Biology, 5, 615-629.
[22] Chang, W.-L. and Guo, M. (2004) Molecular Solutions for the Subset-Sum Problem on DNA-Based Supercomputing. Biosystems, 73, 117-130.
[23] Zhang, D. and Nguyen, D. (1994) PREPARE: A Tool for Knowledge Base Verification. IEEE Transac-tions on Knowledge and Data Engineering, 6, 983-989.
[24] Madahian, B., Deng, L. and Homayouni, R. (2014) Application of Sparse Bayesian Generalized Linear Model to Gene Expression Data for Classification of Prostate Cancer Subtypes. Open Journal of Statistics, 4, 518-526.
[25] Madahian, B. and Faghihi, U. (2014) A Fully Bayesian Sparse Probit Model for Text Categorization. Open Journal of Statistics, 4, 611-619.
[26] Madahian, B., Deng, L. and Homayouni, R. (2014) Development of Sparse Bayesian Multinomial Generalized Linear Model for Multi-Class Prediction. BMC Bioinformatics, 15, P14.
[27] Madahian, B., Klesges, R.C., Klesges, L. and Homayouni, R. (2012) System Dynamics Modeling of Childhood Obesity. BMC Bioinformatics, 13, A13.    eww150215lx


Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / 更改 )

Twitter picture

You are commenting using your Twitter account. Log Out / 更改 )

Facebook photo

You are commenting using your Facebook account. Log Out / 更改 )

Google+ photo

You are commenting using your Google+ account. Log Out / 更改 )

Connecting to %s