Browse wiki

From International Center for Computational Logic
Conjunctive query answering is an importanConjunctive query answering is an important DL reasoning task. Although this task is by now quite well-understood, tight complexity bounds for conjunctive query answering in expressive DLs have never been obtained: all known algorithms run in deterministic double exponential time, but the existing lower bound is only an ExpTime one. In this paper, we prove that conjunctive query answering in ALCI is 2-ExpTime-hard (and thus complete), and that it becomes NExpTime-complete under some reasonable assumptions.omplete under some reasonable assumptions.  +
@inproceedings{ Lutz-DL-07,
  author = {C. {Lutz}},
  booktitle = {Proceedings of the 2007 International Workshop on Description Logics ({DL2007})},
  note = {To appear.},
  series = {CEUR-WS},
  title = {Inverse Roles Make Conjunctive Queries Hard},
  year = {2007},
}
Inproceedings  +
Proceedings of the 2007 International Workshop on Description Logics (DL2007)  +
Lutz-DL07.pdf  +
To appear.  +
Carsten Lutz<br/> '''[[LATPub355|<b>Inverse Roles Make Conjunctive Queries Hard</b>]]Carsten Lutz<br/> '''[[LATPub355|<b>Inverse Roles Make Conjunctive Queries Hard</b>]]''' <br/>__NOTOC__<i>Proceedings of the 2007 International Workshop on Description Logics (DL2007)</i>, CEUR-WS, to appear<br/><span class="fas fa-chevron-right" style="font-size: 85%;" ></span> [[LATPub355|Details]] <span class="fas fa-chevron-right" style="font-size: 85%; margin-left: 2ex; "></span> [[Media:Lutz-DL07.pdf|Download]]Media:Lutz-DL07.pdf|Download]]  +
Carsten Lutz<br/> '''[[LATPub355/en|<b>Inverse Roles Make Conjunctive Queries Hard</b>]]Carsten Lutz<br/> '''[[LATPub355/en|<b>Inverse Roles Make Conjunctive Queries Hard</b>]]''' <br/>__NOTOC__<i>Proceedings of the 2007 International Workshop on Description Logics (DL2007)</i>, CEUR-WS, to appear<br/><span class="fas fa-chevron-right" style="font-size: 85%;" ></span> [[LATPub355|Details]] <span class="fas fa-chevron-right" style="font-size: 85%; margin-left: 2ex;" ></span> [[Media:Lutz-DL07.pdf|Download]]Media:Lutz-DL07.pdf|Download]]  +
CEUR-WS  +
Inverse Roles Make Conjunctive Queries Hard  +
inproceedings  +
2007  +
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.
Inverse Roles Make Conjunctive Queries Hard  +
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.
25. März 2015, 14:34:05  +
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.