On computing minimal and perfect model membership

The computational complexity of a number of problems relating to minimal models of non-Horn deductive databases is considered. In particular, the problem of determining minimal model membership is shown to be NP-complete for non recursive propositional databases. The structure of minimal models is also examined using the notion of a cyclic tree, and methods of determining minimal model membership, minimality of models and compiling the GCWA are presented. The handling of negative premises is also considered using perfect model semantics, and methods for computing perfect model membership are presented.