Reasoning with models

Roni Khardon, Dan Roth

Research output: Chapter in Book/Report/Conference proceedingConference contribution


We develop a model-based approach to reasoning, in which the knowledge base is represented as a set of models (satisfying assignments) rather then 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 fully characterize a set of theories for which the model-based representation is compact and provides efficient reasoning. Theseinclude some 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.

Original languageEnglish (US)
Title of host publicationProceedings of the National Conference on Artificial Intelligence
PublisherAmerican Association for Artificial Intelligence (AAAI) Press
Number of pages6
StatePublished - 1994
Externally publishedYes
EventProceedings of the 12th National Conference on Artificial Intelligence. Part 1 (of 2) - Seattle, WA, USA
Duration: Jul 31 1994Aug 4 1994


OtherProceedings of the 12th National Conference on Artificial Intelligence. Part 1 (of 2)
CitySeattle, WA, USA

ASJC Scopus subject areas

  • Software


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

Cite this