Revisiting conjunctive query entailment for S

Ibanez Garcia, Yazmin ORCID: https://orcid.org/0000-0002-1276-904X, Jung, Jean Christoph, Michielini, Vincent and Murlak, Filip 2026. Revisiting conjunctive query entailment for S. Presented at: 40th AAAI Conference on Artificial Intelligence, Singapore, 20-27 January 2026. Published in: Koeing, Sven, Jenkins, Chad and Taylor, Matthew E. eds. Proceedings of the AAAI Conference on Artificial Intelligence. Proceedings of the AAAI Conference on Artificial Intelligence. , vol.40 (23) Washington, DC, USA: Association for the Advancement of Artificial Intelligence, pp. 19152-19159. 10.1609/aaai.v40i23.38989

Full text not available from this repository.

Abstract

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).

Item Type:	Conference or Workshop Item - published (Paper)
Date Type:	Publication
Status:	Published
Schools:	Schools > Computer Science & Informatics
Publisher:	Association for the Advancement of Artificial Intelligence
ISBN:	9781577359067
ISSN:	2159-5399
Last Modified:	24 Aug 2026 11:37
URI:	https://orca.cardiff.ac.uk/id/eprint/186381

Actions (repository staff only)

Edit Item