×

zbMATH — the first resource for mathematics

Truth maintenance systems and their application for verifying expert system knowledge bases. (English) Zbl 0754.68116
The paper presents the ideas of truth maintenance from three different perspectives:
— Truth maintenance as a database management facility. The original role of a Truth Maintenance System (TMS) was restricted to maintaining belief sets by keeping track and propagating logical dependencies among beliefs which another system, the problemsolver, manipulates. The three best known TMSs — J. Doyle’s [Artif. Intell. (Netherlands) 12, 231-272 (1979)] Justification-based, J. de Kleer’s [Artif. Intell. (Netherlands) 28(2), 127-162 (1986)] Assumption-based TMS, and D. McAllester’s [An outlook on truth maintenance, Technical report, Ai Labortory, Messachusetts Institute of Technology (1980)] Logic-based TMS implement this idea. In the first part the functionality and logical foundations of these systems are discussed, and they are compared in terms of their strengths and limitations.
— Truth maintenance as an inference facility. Extending the basic TMS’s machinery with some reasoning capabilities would allow it to answer a variety of queries about beliefs, not only simple queries about whether a given belief holds or not. Two systems incorporating inference facilities into the basic TMS algorithm are presented in this section: M. Reinfrank’s and O. Dressler’s [Rules and justifications, a uniform approach to reason maintenance and nonmonotonic inference, Proc. International Conference on Fifth Generation Computer Systems ‘88 (1988)] Non-monotonic formal system which is capable of performing inferences in a quasi-first-order logic, and the Contradiction-tolerant TMS [I. Popchev, N. Zlatareva and M. Mircheva, A truth maintenance theory: An alternative approach, Proc. 9th European Conference on AI (ECAI ‘90), Pitman Pub., 509-514 (1990)] which is the only TMS able to explicitly maintain contradictions.
— Truth maintenance as a verification facility. A new promising approach to expert system knowledge bases verification is discussed. It employs the idea of “operationalization” of the knowledge base, i.e. translating it into a special form where all anomalies (such as inconsistencies, redundancies, circularities, etc.) become explicit and thus easy to detect and correct. Two systems, A. Ginsberg’s [Knowledge-best reduction: A new approach to checking knowledge bases for inconsistency and redundancy, Proc. 7th National Conference on Artificial Intelligence (AAAI 88), Vol. 2, 585-589 (1988)] Knowledge base reducer, which incorporate a ATMS-like verification procedure, and N. Zlatareva’s [Considerations on representing and handling human common- sense knowledge. Terso-Report 10, FG Intellektik, Technische Hochschule Darmstadt, Germany (1990)] CTMS-based verification system are presented and compared.
A uniform example is used throughout the paper to make the presentation easier to follow. The paper is addressed to two groups of readers: those who are looking for an introductory survey on TMSs, and those who are interested in non-conventional techniques for expert system knowledge base verification.
Reviewer: N.P.Zlatareva

MSC:
68T35 Theory of languages and software systems (knowledge-based systems, expert systems, etc.) for artificial intelligence
68T30 Knowledge representation
Software:
CENPARMI
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Brewka, G. (1990). On minimal change: A critique of the architecture of non-monotonic TMS. Technical report, GMD, Bonn.
[2] Brown, A. and Shoham, Y. (1989). New results on semantical nonmonotonic reasoning. In Proc. Second Int. Workshop on Non-monotonic Reasoning, pp. 19-26. Springer-Verlag. · Zbl 0675.03008
[3] Buchanan, B. G. and Shortliffe, E. H. (1984). Human engineering of medical expert systems. In Buchanan, B. G. and Shortliffe, E. H. (Eds.), Rule-Based Expert Systems: the MYCIN Experiments of the Stanford Heuristic Programming Project, Ch. 32, pp. 599-612. Addison-Wesley, Reading MA.
[4] deKleer, J. (1986a). An assumption-based TMS. Artificial Intelligence (Netherlands), 28(2), 127-162.
[5] deKleer, J. (1986b). Problem solving with the ATMS. Artificial Intelligence (Netherlands), 28(2), 197-224.
[6] de Kleer, J. and Forbus, K. (1990). Truth Maintenance systems. AAAI. Tutorial on TMS presented at AAAI’90.
[7] Doyle, J. (1979). A truth maintenance system. Artificial Intelligence (Netherlands), 12, 231-272.
[8] Elkan, C. (1990). A rational reconstruction of nonmonotonic truth maintenance systems. Artificial Intelligence (Netherlands), 43, 219-234. · Zbl 0717.68081
[9] Genesereth, M. and Nilsson, N. (1987). Logical Foundations of Artificial Intelligence. Morgan Kaufmann Pub. · Zbl 0645.68104
[10] Ginsberg, A. (1987). A new approach to checking knowledge bases for inconsistency and redundancy. In Proc. 3rd Annual Expert Systems in Government Conference, pp. 102-111.
[11] Ginsberg, A. (1988). Knowledge-base reduction: A new approach to checking knowledge bases for inconsistency and redundancy. In Proc. 7th National Conference on Artificial Intelligence (AAAI 88), Vol. 2, pp. 585-589.
[12] Ginsberg, A. and Williamson, K. (1989). Checking quasi-first-order-logic rule-based systems for inconsistency and redundancy. Technical Report 11354-891229?02TM, AT & T Bell Laboratories, Holmdel, NJ.
[13] Goodwin, J. (1987). A Theory and System for Non-monotonic Reasoning. Ph.D. Thesis, Linkoping University, Sweden.
[14] Junker, U. and Konolige, K. (1990). Computing the extensions of autoepistemic and default theories with a truth maintenance system. In Proc. 8th National Conference on Artificial Intelligence (AAAI ’90), pp. 278-283. Morgan Kaufmann Pub.
[15] Martins, J. (1990). The truth, the whole truth, and nothing but the truth. AI Magazine, Special Issue: 7-25.
[16] Martins, J. and Shapiro, S. (1988). A model for belief revision. Artificial Intelligence (Netherlands), 35(1), 25-79. · Zbl 0646.68109
[17] McAllester, D. (1980). An outlook on truth maintenance. Technical report, AI Laboratory, Massachusetts Institute of Technology.
[18] Nebel, B. (1989). A knowledge level analysis of belief revision. In Proc. First International Conference on Principles of Knowledge Representation and Reasoning, pp. 301-311. Morgan Kaufmann Pub. · Zbl 0709.68091
[19] Nguyen, T. A., Perkins, W. A., Laffey, T. J., and Pecora, D. (1985). Checking an expert systems knowledge base for consistency and completeness. In Proc. 9th International Joint Conference on Artificial Intelligence (IJCAI 85), Vol. 1, pp. 375-378. AAAI.
[20] Petrie, C. (1987). Revised dependency-directed backtracking for default reasoning. In Proc. 6th National Conference on Artificial Intelligence (AAAII ’87), pp. 167-172. Morgan Kaufmann Pub.
[21] Popchev, I., Zlatareva, N., and Mircheva, M. (1990). A truth maintenance theory: An alternative approach. In Proc. 9th European Conference on AI (ECAI ’90), pp. 509-514. Pitman Pub.
[22] Rao, A. and Foo, N. (1989). Formal theories of belief revision. In Proc. First International Conference on Principles of Knowledge Representation and Reasoning, pp. 369-380. Morgan Kaufmann Pub. · Zbl 0709.68094
[23] Reinfrank, M. (1989). Fundamentals and Logical Foundations of Truth Maintenance. Ph.D. Thesis, Linkoping University, Sweden. · Zbl 0718.68070
[24] Reinfrank, M. and Dressler, O. (1988). Rules and justifications, a uniform approach to reason maintenance and nonmonotonic inference. In Proc. International Conference on Fifth Generation Computer Systems ’88.
[25] Reinfrank, M., Dressler, O., and Brewka, G. (1989). On the relationship between truth maintenance and autoepistemic logic. In Proc. 11th International Joint Conference on Artificial Intelligence (IJCAI ’89), pp. 1206-1212. Morgan Kaufmann Pub. · Zbl 0718.68070
[26] Zlatareva, N. (1990). Considerations on representing and handling human common-sense knowledge. TASSO-Report 10, FG Intellektik, Technische Hochschule Darmstadt, Germany.
[27] Zlatareva, N. (1991a). Distributed verification: A new formal approach for verifying knowledge-based systems. In Proc. World Congress on Expert Systems, pp. 1021-1029. Pergamon Press.
[28] Zlatareva, N. (1991b). Truth maintenance and verification of expert system knowledge bases. Technical report, CENPARMI, Concordia University, Montreal, Canada.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.