Date: December 1994
Pages: 77
In this work, a formal model of knowledge representation systems, cautious autoepistemic logic, is investigated. This logic is a variant of autoepistemic logic which is a leading formal approach to knowledge representation systems. Cautious autoepistemic logic has some attractive properties that are not present in its ancestor. Firstly, every set of premises induces a unique set of conclusions. Moreover, this set of conclusions can be characterized iteratively. In this work, a proof theory is developed for cautious autoepistemic logic. The cumulativity of cautious autoepistemic reasoning is studied with the aid of the proof theory. It turns out that cautious autoepistemic reasoning is cumulative in restricted cases. Computational complexity of cautious autoepistemic logic is analyzed. Negative introspection which is the major subtask is shown to be a complete problem on the second level of the polynomial time hierarchy. An upper bound for the computational complexity of cautious autoepistemic reasoning is provided. This implies that such reasoning is in the worst case only slightly more complex than corresponding reasoning in the original autoepistemic logic. As an application, new model theoretic semantics for logic programs is provided in terms of cautious autoepistemic logic. The proposed cautious semantics is compared with the well-founded semantics. Results indicate that the cautious model is more accurate than the well-founded model. An alternative approach is also studied. It leads to a different model that also subsumes the well-founded model.
Keywords: nonmonotonic reasoning, autoepistemic logic, computational complexity, logic programming, well-founded semantics