Models of belief for decidable reasoning in incomplete knowledge bases
Gerhard Lakemeyer · 1992
Since knowledge bases (KBs) are usually incomplete, they should be able to provide information not only about the domain in question but also regarding their own incompleteness, which requires them to introspect on what they know and do not know. One of the challenges is to devise computationally adequate models of introspective KBs, i.e., models where the reasoning task is, at the very least, decidable. Conceptually, introspective reasoning can be formalized very elegantly in terms of a model of belief. In this sense, the corresponding reasoning task is completely characterized as a decision problem of the form: which beliefs follow from believing only the sentences in the KB? Current approaches, the so-called autoepistemic logics, suffer from the idealistic assumption that the reasoner is able to perform perfect logical deduction, which renders the task undecidable when the underlying language is first-order. This thesis develops a logic of belief, which can be used to specify a decidable, and in many cases efficient, form of introspective reasoning in first-order KBs. Decidability is achieved by choosing a model of belief that limits only the deductive component of the reasoner while keeping the full introspective power of existing approaches. The underlying language is a first-order modal dialect that offers both rigid and non-rigid designators, an equality predicate, and quantifying-in. An important feature of the logic is its fairly intuitive model-theoretic semantics, which combines notions from relevance logic and possible-world semantics. While most of the thesis is concerned with the logical and computational properties of belief, we also demonstrate how the logic can be applied to the specification of a decidable knowledge representation service, which offers routines to query a KB and to add new information to it.