Formal Al systems traditionally represent knowledge using logical form
ulas, Sometimes, however, a model-based representation is more compact
and enables faster reasoning than the corresponding formula-based rep
resentation. The central idea behind our work is to represent a large
set of models by a subset of characteristic models. More specifically,
we examine model-based representations of Horn theories, and show tha
t there are large Horn theories that can be exactly represented by an
exponentially smaller set of characteristic models. We show that deduc
tion based on a set of characteristic models requires only polynomial
time, as it does using Horn theories. More surprisingly, abduction can
be performed in polynomial time using a set of characteristic models,
whereas abduction using Horn theories is NP-complete. Finally, we dis
cuss algorithms for generating efficient representations of the Horn t
heory that best approximates a general set of models.