Minimal Knowledge States in Nonmonotonic Modal Logics

Recent studies on the computational properties of the logic of minimal knowledge states due to Halpern and Moses (also known as ground logic S5G ) have shown that reasoning in this logic is strictly harder than in all the most studied propositional nonmonotonic formalisms, in particular with respect to nonmonotonic modal logics due to McDermott and Doyle. In this paper we show that the logic of Halpern and Moses is easily embeddable in most of the modal formalisms of McDermott and Doyle's family. The translation employed provides both for an identification of the source of complexity which makes reasoning harder in minimal knowledge states, and for an analysis of the epistemological properties of this logic, as compared to McDermott and Doyle's formalisms. Thematic area: modal logic and AI/Knowledge Representation. 1 Introduction Research in nonmonotonic modal logics has developed from its early years along two different lines. On the one hand, several studies have proposed the defin..