HORN APPROXIMATIONS OF EMPIRICAL-DATA

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.