Knowledge Compilation for Closed World Reasoning and Circumscription

摘要

This paper presents new complexity results for propositional closed world rasoning (CWR) from tractable knowl- edge 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.