Defeasible Inclusions in Low-Complexity DLs: Preliminary Notes
Proceedings of the Twenty-First International Joint Conference on Artificial Intelligence. Pages 696-700.
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<sub>R</sub> complexity drops from NExp<sup>NP</sup> 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<sup>p<sub>2</sub></sup> and Pi<sup>p<sub>2</sub></sup> for an extension of EL.Piero A. Bonatti, Marco Faella, Luigi Sauro
@inproceedings{ijcai2009p121,
title = {Defeasible Inclusions in Low-Complexity DLs: Preliminary Notes},
author = {Bonatti, Piero A. and Faella, Marco and Sauro, Luigi},
booktitle = {Proceedings of the Twenty-First International Joint Conference on
Artificial Intelligence, {IJCAI-09}},
publisher = {International Joint Conferences on Artificial Intelligence},
editor = {Hiroaki Kitano},
pages = {696--700},
year = {2009},
url = {https://ijcai.org/proceedings/2009/121},
}
TY - CPAPER TI - Defeasible Inclusions in Low-Complexity DLs: Preliminary Notes AU - Bonatti, Piero A. AU - Faella, Marco AU - Sauro, Luigi T2 - Proceedings of the Twenty-First International Joint Conference on Artificial Intelligence, IJCAI-09 PB - International Joint Conferences on Artificial Intelligence PY - 2009 SP - 696 EP - 700 UR - https://ijcai.org/proceedings/2009/121 ER -Copied
Machine-readable versions of this paper, for tools and AI agents:
