@article {IOPORT.05996841,
    author       = {Bonatti, P.A. and Faella, M. and Sauro, L.},
    title        = {Defeasible inclusions in low-complexity DLs.},
    year         = {2011},
    journal      = {The Journal of Artificial Intelligence Research (JAIR)},
    volume       = {42},
    issn         = {1076-9757},
    pages        = {719-764},
    publisher    = {Morgan Kaufmann Publishers, San Francisco, CA},
    doi          = {10.1613/jair.3360},
    abstract     = {The focus of this paper lies mainly on the description logics DL-lite$_R$, $\mathcal{EL}$ and $\mathcal{EL}^\bot$. All accept (binary) role names, (unary) concept names, the full concept $\top$, negations and conjunctions of concepts thanks to the operators $\neg$ and $\sqcap$, and existential concepts of the form $\exists R.C$ for the set of individuals which are in role $R$ with an individual in the extension of concept $C$. The logic $\mathcal{EL}^\bot$ also accepts the empty concept $\bot$. The same holds for the logic DL-lite$_R$, which also accepts nominals to denote individuals and inverses of role names as roles; moreover, it restricts inclusion of concepts $C_L\sqsubseteq C_R$ to $C_L$ being either a concept name or of the form $\exists R.\top$, and to $C_R$ being of the same form or the negation of a concept of the same form. Besides the classical inclusions of concepts, a strict partial order (priority relation) $\preceq$ is defined over general defeasible inclusions (GDIs) $C\sqsubseteq_n D$, which read ``$C$'s elements are normally in $D$'', to make up a defeasible knowledge base $(\mathcal K,\preceq)$. Its models are defined as the maximally $\preceq$-preferred models of its classical part, so using $\preceq$ to resolve conflicts and maximising the set of individuals satisfying the satisfied GDIs. Moreover, maximisation depends on whether concept and role names are allowed to vary or belong to a given set $F$ of such symbols required to remain fixed, which determines a form Circ$_F^{\ast}$ of circumscription, denoted Circ$_F$ when only concept names can be left fixed, with Circ$_{\mathrm{fix}}$ and Circ$_{\mathrm{var}}$ as limiting cases of fixing all or no concept names. The examples given in the paper include User $\sqsubseteq_n$ $\neg\exists$decision.\{Grant\} Staff $\sqsubseteq$ User Staff $\sqsubseteq_n\exists$decision.\{Grant\} BlacklistedStaff $\sqsubseteq$ Staff $\sqcap$ $\neg\exists$decision.\{Grant\} which expresses that users are not granted access (to read project files), unless they are staff and not blacklisted. When $\preceq$ is inclusion (specificity), adding Staff(John) to $\mathcal K$ makes John $\sqsubseteq$ $\exists$decision.\{Grant\} Staff $\sqsubseteq$ John logical consequences of $(\mathcal K,\preceq)$ w.r.t. the Circ$_{\mathrm{var}}$ semantics (the GDI for staff overriding the GDI for user, and maximisation of the set of individuals satisfying both GDIs making John the only staff member), but not w.r.t. the Circ$_{\mathrm{fix}}$ semantics. The core of the paper is devoted to obtaining complexity results for the problems of concept satisfiability (checking whether a concept is not empty in some model), subsumption (checking whether a concept is including in another in all models), and instance checking (checking whether an individual with a given name belongs to the extension of a concept in all models), most particularly w.r.t.\ Circ$_{\mathrm{fix}}$ and Circ$_{\mathrm{var}}$ and for DL-lite$_R$, $\mathcal{EL}^{\bot}$ and $\mathcal{EL}$, with a majority of results for the first two logics. For DL-lite$_R$ and Circ$_{\mathrm{var}}$, concept satisfiability is shown to be $\Sigma_2$ complete while subsumption and instance checking are $\Pi_2$ hard in the polynomial hierarchy; the proof of the last result exploits a similar result for minimal-entailment problem of positive disjunctive programs. For $\mathcal{EL}^{\bot}$, the three problems are shown to be ExpTime hard. Many results are given for fragments of the logics where concept inclusions are instances of specific schemata, meant to in particular, bound quantifier nesting or rule out acyclic terminologies (inclusions between concepts in both directions). The results provide a rather comprehensive picture which well identifies the sources of high complexity, while still leaving open problems listed at the end of the paper.},
    reviewer     = {\'Eric Martin (Sydney)},
    identifier   = {05996841},
}