A Demand-Driven Algorithm for Generating Minimal Models

Knowledge Representation and Reasoning

Volume

Proceedings of the AAAI Conference on Artificial Intelligence, 17

Boolean Satisfiability

The task of generating minimal models of a knowledge base is a significant computational problem in artificial intelligence. This task is at the computational heart of diagnosis systems like truth maintenance systems, and of nonmonotonic systems like autoepistemic logic, default logic, and disjunctive logic programs. Unfortunately, it is NP-hard. In this paper we present a hierarchy of classes of knowledge bases, Psi1, Psi2, ..., with the following properties: first, Psi1 is the class of all Horn knowledge bases; second, if a knowledge base Pi is in Psik, then Pi has at most k minimal models, and all of them may be found in time O(lnk), where l is the length of the knowledge base and n the number of atoms in Pi; third, for an arbitrary knowledge base Pi, we can find the minimum k such that Pi belongs to Psik in time polynomial in the size of Pi ; and, last, where K is the class of all knowledge bases, it is the case that union i=1 infty Psii = K , that is, every knowledge base belongs to some class in the hierarchy. The algorithm is demand-driven, that is, it is capable of generating one model at a time.