Reference:
Tomi Janhunen. Investigations on cautious autoepistemic reasoning. Research Report A31, Helsinki University of Technology, Department of Computer Science and Engineering, Digital Systems Laboratory, Espoo, Finland, December 1994.
Abstract:
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 wellfounded semantics. Results indicate that the cautious model is more accurate than the wellfounded model. An alternative approach is also studied. It leads to a different model that also subsumes the wellfounded model.
Keywords:
nonmonotonic reasoning, autoepistemic logic, computational complexity, logic programming, wellfounded semantics
Suggested BibTeX entry:
@techreport{HUTTCSA31,
address = {Espoo, Finland},
author = {Tomi Janhunen},
institution = {Helsinki University of Technology, Department of Computer Science and Engineering, Digital Systems Laboratory},
month = {December},
number = {A31},
pages = {77},
title = {Investigations on Cautious Autoepistemic Reasoning},
type = {Research Report},
year = {1994},
}
