TY - JOUR

T1 - Reasoning with models

AU - Khardon, Roni

AU - Roth, Dan

N1 - Funding Information:
*An earlier version of the paper appears in the Proceedings of the National Conference on Artificial Intelligence, AAAI-94. * Corresponding author. Research supported by AR0 grant DAAL03-92-G-0115 (Center for Intelligent Control Systems). E-mail: roni@das.harvard.edu. LR esearch supported by NSF grant CCR-92-00884 and by DARPA AFOSR-F4962-92-J-0466. Current address: Department of Applied Mathematics & CS, Weizmann Institute of Science, Rehovot 76100, Israel. E-mail: danr@wisdom.weizmann.ac.il.

PY - 1996/11

Y1 - 1996/11

N2 - We develop a model-based approach to reasoning, in which the knowledge base is represented as a set of models (satisfying assignments) rather than a logical formula, and the set of queries is restricted. We show that for every propositional knowledge base (KB) there exists a set of characteristic models with the property that a query is true in KB if and only if it is satisfied by the models in this set. We characterize a set of functions for which the model-based representation is compact and provides efficient reasoning. These include cases where the formula-based representation does not support efficient reasoning. In addition, we consider the model-based approach to abductive reasoning and show that for any propositional KB, reasoning with its model-based representation yields an abductive explanation in time that is polynomial in its size. Some of our technical results make use of the monotone theory, a new characterization of Boolean functions recently introduced. The notion of restricted queries is inherent in our approach. This is a wide class of queries for which reasoning is efficient and exact, even when the model-based representation KB provides only an approximate representation of the domain in question. Moreover, we show that the theory developed here generalizes the model-based approach to reasoning with Horn expressions and captures even the notion of reasoning with Horn approximations.

AB - We develop a model-based approach to reasoning, in which the knowledge base is represented as a set of models (satisfying assignments) rather than a logical formula, and the set of queries is restricted. We show that for every propositional knowledge base (KB) there exists a set of characteristic models with the property that a query is true in KB if and only if it is satisfied by the models in this set. We characterize a set of functions for which the model-based representation is compact and provides efficient reasoning. These include cases where the formula-based representation does not support efficient reasoning. In addition, we consider the model-based approach to abductive reasoning and show that for any propositional KB, reasoning with its model-based representation yields an abductive explanation in time that is polynomial in its size. Some of our technical results make use of the monotone theory, a new characterization of Boolean functions recently introduced. The notion of restricted queries is inherent in our approach. This is a wide class of queries for which reasoning is efficient and exact, even when the model-based representation KB provides only an approximate representation of the domain in question. Moreover, we show that the theory developed here generalizes the model-based approach to reasoning with Horn expressions and captures even the notion of reasoning with Horn approximations.

KW - Automated reasoning

KW - Common-sense reasoning

KW - Knowledge representation

UR - http://www.scopus.com/inward/record.url?scp=0030288991&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0030288991&partnerID=8YFLogxK

U2 - 10.1016/s0004-3702(96)00006-9

DO - 10.1016/s0004-3702(96)00006-9

M3 - Article

AN - SCOPUS:0030288991

VL - 87

SP - 187

EP - 213

JO - Artificial Intelligence

JF - Artificial Intelligence

SN - 0004-3702

IS - 1-2

ER -