A rational reconstruction of nonmonotonic truth maintenance systems

摘要

The main contribution of this paper is a precise characterization of the inferences performed by nonmonotonic truth maintenance systems (TMSs), using two standard nonmonotonic formalisms: logic programming with the stable set semantics and autoepistemic logic. The paper also contains an analysis of the role of dependency-directed backtracking in dealing with contradictions, and a proof that implementing a nonmonotonic TMS is an NP-complete problem.