Complexity Results for Propositional Closed World Reasoning and Circumscription from Tractable Knowledge Bases
Abstract
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 laid 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. Our results suggest knowledge compilation as a valuable approach to deal with the complexity of CWR in some situations.
Cite
Text
Coste-Marquis and Marquis. "Complexity Results for Propositional Closed World Reasoning and Circumscription from Tractable Knowledge Bases." International Joint Conference on Artificial Intelligence, 1999.Markdown
[Coste-Marquis and Marquis. "Complexity Results for Propositional Closed World Reasoning and Circumscription from Tractable Knowledge Bases." International Joint Conference on Artificial Intelligence, 1999.](https://mlanthology.org/ijcai/1999/costemarquis1999ijcai-complexity/)BibTeX
@inproceedings{costemarquis1999ijcai-complexity,
title = {{Complexity Results for Propositional Closed World Reasoning and Circumscription from Tractable Knowledge Bases}},
author = {Coste-Marquis, Sylvie and Marquis, Pierre},
booktitle = {International Joint Conference on Artificial Intelligence},
year = {1999},
pages = {24-29},
url = {https://mlanthology.org/ijcai/1999/costemarquis1999ijcai-complexity/}
}