跳至主要内容

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

Read  full  paper  at:
http://www.scirp.org/journal/PaperInformation.aspx?PaperID=54046#.VOBRQizQrzE

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.
 
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.
 
References
[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.
http://dx.doi.org/10.1109/TKDE.2007.190743
 
[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.
http://dx.doi.org/10.1109/69.494164
 
[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.
http://dx.doi.org/10.1109/TKDE.2003.1185845
 
[4]Ligeza, A. (2006) Logical Foundations for Rule-Based Systems. Springer, New York, 189-211.
http://dx.doi.org/10.1007/3-540-32446-1_12
 
[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.
http://dx.doi.org/10.1109/TKDE.2006.96
 
[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.http://dx.doi.org/10.1016/S0020-7373(87)80076-7
 
[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.
http://dx.doi.org/10.1109/69.591448
 
[11]Nazareth, D.L. and Kennedy, M.H. (1991) Verification of Rule-Based Knowledge Using Directed Graphs. Knowledge Acquisition, 3, 339-360. http://dx.doi.org/10.1016/S1042-8143(05)80024-X
 
[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.
http://dx.doi.org/10.1109/69.224193
 
[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.
http://dx.doi.org/10.1016/0020-7373(92)90043-K
 
[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.http://dx.doi.org/10.1126/science.7973651
 
[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.
http://dx.doi.org/10.1073/pnas.83.11.3746
 
[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.http://dx.doi.org/10.1089/cmb.1998.5.615
 
[22]Chang, W.-L. and Guo, M. (2004) Molecular Solutions for the Subset-Sum Problem on DNA-Based Supercomputing. Biosystems, 73, 117-130. http://dx.doi.org/10.1016/j.biosystems.2003.11.001
 
[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.http://dx.doi.org/10.4236/ojs.2014.47049
 
[25]Madahian, B. and Faghihi, U. (2014) A Fully Bayesian Sparse Probit Model for Text Categorization. Open Journal of Statistics, 4, 611-619. http://dx.doi.org/10.4236/ojs.2014.48057
 
[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.
http://dx.doi.org/10.1186/1471-2105-15-S10-P14
 
[27]Madahian, B., Klesges, R.C., Klesges, L. and Homayouni, R. (2012) System Dynamics Modeling of Childhood Obesity. BMC Bioinformatics, 13, A13. http://dx.doi.org/10.1186/1471-2105-13-S12-A13    eww150215lx
标签：

评论

发表评论

此博客中的热门博文

Does Immigration Promote the Investment of the Monopolistic Firm?

In the present paper, we examine the effect of increasing uncertainty of immigrants’ growth on the optimal timing of investment of a firm that has a monopolistic power over the labor market. It is revealed that when the uncertainty of immigrants’ growth is more than a threshold level, increasing uncertainty of immigrants’ growth accelerates the optimal timing of firms’ investment and enhances the economic growth, even if the uncertainty of immigrants’ growth is formulated by the geometric Brownian motion, which is in sharp contrast to the standard result that an increase in the uncertainty postpones the optimal timing. With an increase in the immigrants over the past ten years, workforces in the host countries have been growing significantly to the extent that the immigrants represent 70% of the increase in the workforce in Europe, and 47% in the United States as OECD indicates. In the present paper, we attempted to investigate the effect of increased uncertainty caused by the growi...
发表评论
阅读全文

Education Policy Implementation: A Mechanism for Enhancing Primary Education Development in Zanzibar

Education is one of the fundamental rights of individuals; therefore, the government of a country needs to develop and strengthen educational policy and quality as well as to ensure that everyone has equal access to basic education. The improvement of access and quality of education in the world is becoming as an essential factor in development, whereas the basic education (primary school), is acknowledged as a foundation of the higher educational development for every country. To fulfill this goal, governments introduce several policies and procedures; however, it requires some reforms and participation from the politician, policymakers, and other stakeholders to re-examine educational policy so that it can lead to multiplication and betterment of the reforms. Educational reforms actually focus on accountability. A positive educational development and reform is very challenging and needs more effort and strategy on how to use and utilize the resources effectively as such it can achie...
发表评论
阅读全文