On computing minimal and perfect model membership |
| |
Authors: | CA Johnson |
| |
Affiliation: | Computer Science Department, University of Keele, Staffordshire, ST5 5BG, UK |
| |
Abstract: | 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. |
| |
Keywords: | Deductive databases Indefinite data Generalised closed world assumption Complexity Minimal Model Perfect model Cyclic tree |
本文献已被 ScienceDirect 等数据库收录! |
|