Weak Autoepistemic Reasoning and Well-Founded Semantics.
Jürgen Kalinski · 1992
The appropriateness of Autoepistemic Logic for the construction of knowledge representation systems is regarded as questionable due to its great computational complexity. Instead of resorting to incomplete interpreters, we propose a semantical characterization of approximate autoepistemic reasoning. It consists of a sequence of monotonically decreasing sets of belief states. Every autoepistemic expansion is a maximal fixpoint and is contained in the smallest fixpoint. For stratified knowledge bases the approach coincides with Autoepistemic Logic. For normal and disjunctive rules the construction can be reduced to iterated applications of a specialized consequence operator for the underlying monotonic logic. For normal rules the approximation coincides with the well-founded semantics on atomic propositions. Hence, it can be computed in quadratic time in this case.