Truth maintenance systems and their application for verifying expert system knowledge bases (Q1193853)

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 --- \textit{J. Doyle's} [Artif. Intell. (Netherlands) 12, 231-272 (1979)] Justification-based, \textit{J. de Kleer's} [Artif. Intell. (Netherlands) 28(2), 127-162 (1986)] Assumption-based TMS, and \textit{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: \textit{M. Reinfrank's} and \textit{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 [\textit{I. Popchev}, \textit{N. Zlatareva} and \textit{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, \textit{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 \textit{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.