Browse wiki
From International Center for Computational Logic
It is commonly known that the conjunctive … It is commonly known that the conjunctive query entailment problem for certain ex- tensions of (the well-known ontology language) ALC is computationally harder than their knowledge base satisfiability problem while for others the complexities coincide, both under the standard and the finite-model semantics. We expose a uniform principle behind this divide by identifying a wide class of (finitely) locally-forward description logics, for which we prove that (finite) query entailment problem can be solved by a reduction to exponentially many calls of the (finite) knowledge base satisfiability problem. Consequently, our algorithm yields tight ExpTime upper bounds for locally-forward logics with ExpTime-complete knowledge base satisfiability problem, including logics between ALC and μALCHbregQ (and more), as well as ALCSCC with global cardinality constraints, for which the complexity of querying remained open. Moreover, to make our technique applicable in future research, we provide easy-to-check sufficient conditions for a logic to be locally-forward based on several novel versions of the model-theoretic notion of unravellings.</br>Together with existing results, this provides a nearly complete classification of the “benign” vs. “malign” primitive modelling features extending ALC, missing out only the Self operator. We then show a rather surprising result, namely that the conjunctive entailment problem for ALCSelf is exponentially harder than for ALC. This places the seemingly innocuous Self operator among the “malign” modelling features, like inverses, transitivity or nominals., like inverses, transitivity or nominals. +
@article{BR2023,
author = {Bartosz Bednarczyk and Sebastian Rudolph},
title = {How to Tell Easy from Hard: Complexities of Conjunctive Query
Entailment in Extensions of {ALC}},
journal = {Journal of Artificial Intelligence Research},
volume = {78},
year = {2023},
month = {November},
pages = {385{\textendash}458},
doi = {https://doi.org/10.1613/jair.1.14482}
}
author = {Bartosz Bednarczyk and Sebastian Rudolph},
title = {How to Tell Easy from Hard: Complexities of Conjunctive Query
Entailment in Extensions of {ALC}},
journal = {Journal of Artificial Intelligence Research},
volume = {78},
year = {2023},
month = {November},
pages = {385{\textendash}458},
doi = {https://doi.org/10.1613/jair.1.14482}
}
Bednarczyk +
Bartosz +
Bartosz Bednarczyk, Sebastian Rudolph<b … Bartosz Bednarczyk, Sebastian Rudolph<br/> '''[[Article3095|How to Tell Easy from Hard: Complexities of Conjunctive Query Entailment in Extensions of ALC]]''' <br/>__NOTOC__Journal of Artificial Intelligence Research, 78:385–458, November 2023<br/><span class="fas fa-chevron-right" style="font-size: 85%;" ></span> [[Article3095|Details]] <span class="fas fa-chevron-right" style="font-size: 85%; margin-left: 2ex; "></span> [[Media:BBESRU2023JAIR-final.pdf|Download]]a:BBESRU2023JAIR-final.pdf|Download]] +
Bartosz Bednarczyk, Sebastian Rudolph<b … Bartosz Bednarczyk, Sebastian Rudolph<br/> '''[[Article3095/en|How to Tell Easy from Hard: Complexities of Conjunctive Query Entailment in Extensions of ALC]]''' <br/>__NOTOC__Journal of Artificial Intelligence Research, 78:385–458, November 2023<br/><span class="fas fa-chevron-right" style="font-size: 85%;" ></span> [[Article3095|Details]] <span class="fas fa-chevron-right" style="font-size: 85%; margin-left: 2ex;" ></span> [[Media:BBESRU2023JAIR-final.pdf|Download]]a:BBESRU2023JAIR-final.pdf|Download]] +
How to Tell Easy from Hard: Complexities of Conjunctive Query Entailment in Extensions of ALC +
Anzeigetitel„Anzeigetitel <span style="font-size:small;">(Display title of)</span>“ ist ein softwareseitig fest definiertes Attribut, das einen eindeutigen Anzeigetitel zu einem Objekt speichert und ihm zuweist. Es wird von <a rel="nofollow" class="external text" href="https://www.semantic-mediawiki.org/wiki/Help:Special_properties">Semantic MediaWiki</a> zur Verfügung gestellt.
How to Tell Easy from Hard: Complexities of Conjunctive Query Entailment in Extensions of ALC +
Zuletzt geändert„Zuletzt geändert <span style="font-size:small;">(Modification date)</span>“ ist ein softwareseitig fest definiertes Attribut, das das Datum der letzten Änderung einer Seite speichert. Es wird von <a rel="nofollow" class="external text" href="https://www.semantic-mediawiki.org/wiki/Help:Special_properties">Semantic MediaWiki</a> zur Verfügung gestellt.
20. November 2023, 08:10:35 +
Hat Abfrage„Hat Abfrage <span style="font-size:small;">(Has query)</span>“ ist ein softwareseitig fest definiertes Attribut, das die Metainformationen einer Abfrage als <a rel="nofollow" class="external text" href="https://www.semantic-mediawiki.org/wiki/Subobject">Subobjekt</a> speichert. Es wird von <a rel="nofollow" class="external text" href="https://www.semantic-mediawiki.org/wiki/Help:Special_properties">Semantic MediaWiki</a> zur Verfügung gestellt.
How to Tell Easy from Hard: Complexities of Conjunctive Query Entailment in Extensions of ALC +, How to Tell Easy from Hard: Complexities of Conjunctive Query Entailment in Extensions of ALC +, How to Tell Easy from Hard: Complexities of Conjunctive Query Entailment in Extensions of ALC +, How to Tell Easy from Hard: Complexities of Conjunctive Query Entailment in Extensions of ALC +, How to Tell Easy from Hard: Complexities of Conjunctive Query Entailment in Extensions of ALC + und How to Tell Easy from Hard: Complexities of Conjunctive Query Entailment in Extensions of ALC +
