Reasoning with models

Roni Khardon, Dan Roth

Research output: Contribution to journalArticlepeer-review

Abstract

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.

Original languageEnglish (US)
Pages (from-to)187-213
Number of pages27
JournalArtificial Intelligence
Volume87
Issue number1-2
DOIs
StatePublished - Nov 1996

Keywords

  • Automated reasoning
  • Common-sense reasoning
  • Knowledge representation

ASJC Scopus subject areas

  • Language and Linguistics
  • Linguistics and Language
  • Artificial Intelligence

Fingerprint

Dive into the research topics of 'Reasoning with models'. Together they form a unique fingerprint.

Cite this