EUVIMEDEUVIMED entdecken
Crossref

Revisiting Conjunctive Query Entailment for S

Yazmín Ibáñez-García, Jean Christoph Jung, Vincent Michielini, Filip Murlak

Proceedings of the AAAI Conference on Artificial Intelligence · 14.03.2026 · 40 (23) · 19152-19159

DOI: 10.1609/aaai.v40i23.38989 ↗

Kurz gefasst

Fachartikel in der Zeitschrift Proceedings of the AAAI Conference on Artificial Intelligence, online erschienen am 14.03.2026. Verfasst von Yazmín Ibáñez-García und 3 weiteren Autor:innen.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

We clarify the complexity of answering unions of conjunctive queries over knowledge bases formulated in the description logic S, the extension of ALC with transitive roles. Contrary to what existing partial results suggested, we show that the problem is, in fact, 2ExpTime-complete; hardness already holds in the presence of two transitive roles and for Boolean conjunctive queries. We complement this result by showing that the problem remains in coNExpTime when the input query is rooted or is restricted to use at most one transitive role (but may use arbitrarily many non-transitive roles).

Zitieren

APA

Ibáñez-García, Y., Jung, J. C., Michielini, V., & Murlak, F. (2026). Revisiting Conjunctive Query Entailment for S. Proceedings of the AAAI Conference on Artificial Intelligence, 40(23), 19152-19159. https://doi.org/10.1609/aaai.v40i23.38989

Vancouver

Ibáñez-García Y, Jung JC, Michielini V, Murlak F. Revisiting Conjunctive Query Entailment for S. Proceedings of the AAAI Conference on Artificial Intelligence. 2026;40(23):19152-19159. doi:10.1609/aaai.v40i23.38989

BibTeX
@article{IbezGarca2026,
  author = {Ibáñez-García, Yazmín and Jung, Jean Christoph and Michielini, Vincent and Murlak, Filip},
  title = {Revisiting Conjunctive Query Entailment for S},
  journal = {Proceedings of the AAAI Conference on Artificial Intelligence},
  year = {2026},
  volume = {40},
  number = {23},
  pages = {19152--19159},
  doi = {10.1609/aaai.v40i23.38989}
}
Kostenlos starten →