Truth Maintenance System

Context:
- It can maintain reasoning results, intermediate results, and deduction relations among them.
See: Knowledge Representation, Belief Revision System, Completion-based Algorithm, Term Rewriting System.

References

(Wikipedia - TMS, 2011-Jun-23) ⇒ http://en.wikipedia.org/wiki/Truth_maintenance_system
- A truth maintenance system, or TMS, is a knowledge representation method for representing both beliefs and their dependencies. The name truth maintenance is due to the ability of these systems to restore consistency. It is also termed as a belief revision system, a truth maintenance system maintains consistency between old believed knowledge and current believed knowledge in the knowledge base (KB) through revision. If the current believed statements contradict the knowledge in KB, then the KB is updated with the new knowledge. It may happen that the same data will again come into existence, and the previous knowledge will be required in KB. If the previous data is not present, it is required for new inference. But if the previous knowledge was in the KB, then no retracing of the same knowledge was needed. Hence the use of TMS to avoid such retracing; it keeps track of the contradictory data with the help of a dependency record. This record reflects the retractions and additions which makes the inference engine (IE) aware of its current belief set. ... There are two types of justification for each node. They are: Support List [SL] and Conceptual Dependencies(CP) ...

(Everett & Forbus, 1996) ⇒ John O. Everett, and Kenneth D. Forbus. (1996). “Scaling up Logic-based Truth Maintenance Systems via Fact Garbage Collection.” In: Proceedings of AAAI 1996 (AAAI-1996).
- QUOTE: TMSs provide valuable explanatory services to automated reasoners. However, this ability comes at the price of a monotonic increase in the size of the dependency network as new assumptions are added. We have found that this memory demand characteristic can result in performance degradation and even software crashes in fielded applications, when the dependency network expands to fill available memory.

(Bridgeland & Huhns, 1990) ⇒ D. M. Bridgeland, and M. N. Huhns. (1990). “Distributed Truth Maintenance.” In: Proceedings of the Eighth National Conference on Artificial Intelligence (AAAI 1990).

(Martins & Shapiro, 1988) ⇒ J. P. Martins and S. C. Shapiro. (1988). “A model for belief revision.” In: Artif. Intell. 35(1). doi:10.1016/0004-3702(88)90031-8

(de Kleer, 1986) ⇒ J. de Kleer. (1986). “An assumption-based TMS." Artificial Intelligence, 28.

(Doyle, 1979) ⇒ Jon Doyle. (1979). “A Truth Maintenance System.” In: Artificial Intelligence, 12(3).
- ABSTRACT: To choose their actions, reasoning programs must be able to make assumptions and subsequently revise their beliefs when discoveries contradict these assumptions. The Truth Maintenance System (TMS) is a problem solver subsystem for performing these functions by recording and maintaining the reasons for program beliefs. Such recorded reasons are useful in constructing explanations of program actions and in guiding the course of action of a problem solver. This paper describes (1) the representations and structure of the Image, (2) the mechanisms used to revise the current set of beliefs, (3) how dependency-directed backtracking changes the current set of assumptions, (4) techniques for summarizing explanations of beliefs, (5) how to organize problem solvers into “dialectically arguing” modules, (6) how to revise models of the belief systems of others, and (7) methods for embedding control structures in patterns of assumptions. We stress the need of problem solvers to choose between alternative systems of beliefs, and outline a mechanism by which a problem solver can employ rules guiding choices of what to believe, what to want, and what to do.