Defeasible Inclusions in Low-Complexity DLs: Preliminary Notes
Abstract
We analyze the complexity of reasoning with circumscribed low-complexity DLs such as DL-lite and the EL family, under suitable restrictions on the use of abnormality predicates. We prove that in circumscribed DL-lite$_{R}$ complexity drops from NExp$^{NP}$ to the second level of the polynomial hierarchy. In EL, reasoning remains ExpTime-hard, in general. However, by restricting the possible occurrences of existential restrictions, we obtain membership in Sigma$^{p$_2$}$ and Pi$^{p$_2$}$ for an extension of EL. Piero A. Bonatti, Marco Faella, Luigi Sauro
Cite
Text
Bonatti et al. "Defeasible Inclusions in Low-Complexity DLs: Preliminary Notes." International Joint Conference on Artificial Intelligence, 2009.Markdown
[Bonatti et al. "Defeasible Inclusions in Low-Complexity DLs: Preliminary Notes." International Joint Conference on Artificial Intelligence, 2009.](https://mlanthology.org/ijcai/2009/bonatti2009ijcai-defeasible/)BibTeX
@inproceedings{bonatti2009ijcai-defeasible,
title = {{Defeasible Inclusions in Low-Complexity DLs: Preliminary Notes}},
author = {Bonatti, Piero A. and Faella, Marco and Sauro, Luigi},
booktitle = {International Joint Conference on Artificial Intelligence},
year = {2009},
pages = {696-701},
url = {https://mlanthology.org/ijcai/2009/bonatti2009ijcai-defeasible/}
}