---
title: "Defeasible Inclusions in Low-Complexity DLs: Preliminary Notes"
authors:
  - "Piero A. Bonatti"
  - "Marco Faella"
  - "Luigi Sauro"
doi: ""
url: "https://ijcai.org/proceedings/2009/121"
pdf: "https://ijcai.org/proceedings/2009/0121.pdf"
venue: "Proceedings of the Twenty-First International Joint Conference on Artificial Intelligence"
year: 2009
pages: "696-700"
track: ""
keywords:
---

# Defeasible Inclusions in Low-Complexity DLs: Preliminary Notes

Piero A. Bonatti, Marco Faella, Luigi Sauro

*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