Investigations on Cautious Autoepistemic Reasoning


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.


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.


nonmonotonic reasoning, autoepistemic logic, computational complexity, logic programming, well-founded semantics

Suggested BibTeX entry:

    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},

NOTE: Reprint of Licentiate's thesis; see URL below.
PostScript (727 kB)
GZipped PostScript (203 kB)
See ...