CHECKER: an efficient algorithm for knowledge base verification

ABSTRACT

MIDST (Mixed Inferencing Dempster Shafer Tool) is a rule-based expert system shell that incorporates mixed-initiative reasoning and uncertain reasoning based on the Dempster Shafer evidence combination scheme. This paper discusses the CHECKER program, a subcomponent of MIDST, which makes use of the existing rule network structure to check the consistency and completeness of the MIDST knowledge base in a efficient manner.

REFERENCES

• 1: D.A. Waterman and F. Hayes-Roth, "An Investigation of Tools for Building Expert Systems", from Building Expert Systems, F. Hayes-Rot}l, D.A. Waterman, and D.B. Lenat, eds., pp. 169-215, Addison-Weseley, Reading, MA, 1983.
• 2: Paul Harmon , David King, Expert systems: artificial intelligence in business, John Wiley & Sons, Inc., New York, NY, 1985
• 3: William Mettrey, An assessment of tools for building large KB systems, AI Magazine, v.8 n.4, p.81-89, Winter 1987
• 4: R. Davis, "TEIRESIAS: Applications of Meta Level Knowledge", from Knowledge-Based Systems in Artificial Intelligence, (by R. Davis and D.B. Lenat), pp. 229-484, McGraw Hill, New York, 1983.
• 5: Suwa, M., Scott, A. C., and Shortliffe, E. H., "Completeness and Consistency in a Rule-based System", Rule-Base Expert Systems, pp. 159-170, 1984.
• 6: Reid G. Smith, Howard A. Winston, Tom M. Mitchell and Bruce G. Buchanan, "Representation and Use of Explicit Justifications for Knowledge Base Refinement", Proceedings AAAI, 1987.
• 7: G. Bisw~s ~nd T.S. Anand, "Using the Dempster- Sharer Scheme in a Diagnostic Expert System Shell", Proceedings of the Third Workshop on Artificla} Intelligence, Seattle. $VA. pp. 98-105, 1987.
• 8: G. Biswas, W.J. Itagins. and X. Yu, "Updates to MIDST' An Expert System Shell for Mixed Initiative Reasoning", Technical Report. 88-15, Vanderbilt University, Nashville. TN.. 1988.
• 9: Till A. N guyen, W. A. Perkins, T. J. Laffey and D. pecora. "Checking An Expert Systems Knowledge Base For Consistency And Completeness", Proceedings of the Ninth International Joint Conference on Ai, pp. 375-378, Los Angeles, CA., 1985.
• 10: Tin A. Nguyen. "Verifying Consistency of Production Systems", Proceedings of the Third Conference on Artificial Intelligence Applications, pp. 4-8, Washington D.C. 198 7.
• 11: Brian J. Cragun , Harold J. Steudel, A decision-table-used processor for checking completeness and consistency in rule-based expert systems, International Journal of Man-Machine Studies, v.26 n.5, p.633-648, May 1, 1987 [doi>10.1016/S0020-7373(87)80076-7]
• 12: Tin A Nguyen , Walton Perkin , Thomas J Laffey , Deanne Pecora, Knowledge base verification, AI Magazine, v.8 n.2, p.69-75, Summer 1987
• 13: G. Shafer, A Mathematical Theory of Evidence, Princeton University Press, NJ, 1988.
• 14: G. Biswas and T.S. Anand, "An Expert System Shell for ML-zed-initiative Reasoning", Journal of the Indian Institute of Science. pp. 465 - 490, 1987.
• 15: Gautam Biswas , Michael Oliff , Robert Abramczyk, OASES (Operations Analysis Expert System): an application in fiberglass manufacturing, International Journal of Expert Systems, v.1 n.3, p.193-216, Sept. 1988
• 16: G. Biswas, C.G.S.C. Kendall, R.L. Cannon, and J.C. Bezdek. "XX' Hydrocarbon Exploration using a Knowledge Based Approach", Tech. Report, Dept. of Computer Science, Univ. of South Carolina, Columbia, S.C., 1988.
• 17: David C. Wilkins and Bruce G. Buchanan, "On Debugging Rule Sets When Reasoning Under Uncertainty", Proceedings AAAI-86, pp. 448-454, Philadelphia, PA, 1986.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.4 Knowledge Representation Formalisms and Methods
          Subjects: Representations (procedural and rule-based)

Additional Classification:
  C. Computer Systems Organization
  C.4 PERFORMANCE OF SYSTEMS
      Subjects: Reliability, availability, and serviceability

  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.5 Programming Languages and Software
          Subjects: Expert system tools and techniques

General Terms:
Algorithms, Design, Performance, Verification