Ground Nonmonotonic Modal Logics for Knowledge Representation

In this paper we discuss ground logics, a family of nonmonotonic modal logics, with the goal of using them in knowledge representation. Ground logics are based on the idea of minimizing the knowledge expressed by non-modal formulae. The nonmonotonic character of the logics can be described either by a fix-point equation or by means of a preference relation on possible-worlds models. We address both the epistemological and the computational properties of ground logics. We discuss their representational features and provide a thorough comparison with McDermott and Doyle logics. Then, we show that reasoning in ground logics is \Pi p 3 -hard, and prove that \Pi p 3 is also an upper bound for reasoning in the major ground logics. Moreover, we identify some special cases where the complexity of reasoning in ground logics is lower than in the general case. Keywords: knowledge representation, nonmonotonic logics, logics of knowledge, computational complexity, reasoning. 1 Introduction No..