A truth maintenance system (TMS) is a general problem solving facility designed to work in tandem with an inference engine. Justification-based TMSs do not have sufficient expressive power for many applications. Logic-based TMSs overcome this limitation but are untractable. Therefore, D. A. McAllester (1980) and K. Forbus and J. de Kleer (1991), have proposed to encode formulas in clauses and to run the efficient Boolean constraint propagation algorithm (BCP), which loses the completeness of the deductions. The author introduces the model of constraint networks (CNs), underlining that the notion of local completeness, called local-consistency in CNs, has been widely treated in CNs. An encoding of McAllester's TMS in a dynamic CN is proposed to be able to use CN techniques. It is shown that, not only can as many deductions be computed as with BCP for the same time-consumption, but also superior performance can be obtained for the local completeness computed for a slightly longer running-time.
展开▼
机译：真理维护系统（TMS）是一种通用的解决问题的工具，旨在与推理引擎协同工作。基于对齐的TMS对于许多应用程序都没有足够的表达能力。基于逻辑的TMS克服了此限制，但难以处理。因此，D。A. McAllester（1980）和K. Forbus和J. de Kleer（1991）提出了对子句中的公式进行编码并运行有效的布尔约束传播算法（BCP），这会丢失推论的完整性。作者介绍了约束网络（CN）的模型，强调了局部完整性的概念，即CN中的局部一致性，已经在CN中得到了广泛的对待。提议在动态CN中对McAllester的TMS进行编码，以能够使用CN技术。结果表明，对于相同的时间消耗，不仅可以计算出与BCP一样多的推导，而且对于稍长的运行时间所计算出的局部完整性，也可以获得较高的性能。
展开▼
