Reducing Query Answering to Satisfiability in Nonmonotonic Logics

Abstract

We propose a unifying view of negation as failure, integrity constraints, and epistemic queries in nonmonotonic reason-ing. Specifically, we study the relationship between satisfia-bility and logical implication in nonmonotonic logics, show-ing that, in many nonmonotonic formalisms, it is possible and easy to reduce logical implication to satisfiability. This result not only allows for establishing new complexity re-sults for the satisfiability problem in nonmonotonic logics, but also establishes a clear relationship between the stud-ies on epistemic queries and integrity constraints in mono-tonic knowledge bases with the work on negation by default in nonmonotonic reasoning and logic programming. From the perspective of the design of knowledge representation systems, such a reduction allows for defining both a simple method for answering epistemic queries in knowledge bases with nonmonotonic abilities, and a procedure for identify-ing integrity constraints in the knowledge base, which can be employed for optimizing reasoning in such systems.