Journal of Logic and Computation, Volume 11, Issue 4, pp. 579-607: Abstract.
Knowledge Compilation for Closed World Reasoning and Circumscription
Sylvie Coste-Marquis1, and Pierre Marquis2
1CRIL IUT de Lens/Université d'Artois, rue de l'Université-S.P. 16, F-62307 Lens Cedex, France. E-mail: firstname.lastname@example.org
This paper presents new complexity results for propositional closed world reasoning (CWR) from tractable knowledge bases (KBs). Both (basic) CWR, generalized CWR, extended generalized CWR, careful CWR and extended CWR (equivalent to circumscription) are considered. The focus is on tractable KBs belonging to target classes for exact compilation functions: Blake formulas, DNFs, disjunctions of Horn formulas, and disjunctions of renamable Horn formulas. The complexity of inference is identified for all the forms of CWR listed above. For each of them, new tractable fragments are exhibited. Interestingly, the restricted classes of formulas we consider are target classes for exact compilation functions, i.e., every KB can be turned into an equivalent formula from any of these classes. Accordingly, our results suggest knowledge compilation as a valuable, practical approach to deal with the complexity of CWR in some situations.
Keywords: Closed world reasoning, circumscription, knowledge compilation