Only Knowing with Confidence Levels: Reductions and Complexity

Abstract

An important problem in nonmonotonic reasoning is deciding what the precise beliefs of an agent might be, given an incomplete specification. The notion of a stable expansion of an autoepistemic theory is a way of capturing this. As autoepistemic logic is not a logic per se, to actually find the stable expansions, one cannot do this on the object level, but has to use an algorithm involving meta-concepts like set inclusion. Levesque's ``Only knowing'' logic can be used to represent autoepistemic theories, with the benefit of finding the expansions within the logic, on the object level. Waaler's logic Æ generalizes this logic, adding confidence levels. We show how a generalization of stable expansions can be found, strictly using equivalences in Æ, thus providing a rewriting procedure. In Ch. 2, we introduce Æ and the related Æ_\rho. In Ch. 3, we give three rewriting procedures for the case when there is only one confidence level. In Ch. 4 we give a rewriting procedure for the general case with multiple confidence levels. In Ch. 5 we examine the complexity of the problem of deciding whether expansions exist, and give an algorithm for generating them.