Cardiff University | Prifysgol Caerdydd ORCA
Online Research @ Cardiff 
WelshClear Cookie - decide language by browser settings

Answering regular path queries mediated by unrestricted SQ ontologies

Gutierrez Basulto, Victor ORCID:, Ibanez Garcia, Yazmin ORCID:, Jung, Jean Christoph and Murlak, Filip 2023. Answering regular path queries mediated by unrestricted SQ ontologies. Artificial Intelligence 314 , 103808. 10.1016/j.artint.2022.103808

[thumbnail of 1-s2.0-S0004370222001485-main.pdf] PDF - Published Version
Available under License Creative Commons Attribution.

Download (660kB)


A prime application of description logics is ontology-mediated query answering, with the query language often reaching far beyond instance queries. Here, we investigate this task for positive existential two-way regular path queries and ontologies formulated in the expressive description logic , where denotes the extension of the basic description logic with transitive roles () and qualified number restrictions () which can be unrestrictedly applied to both non-transitive and transitive roles (). Notably, the latter is usually forbidden in expressive description logics. As the main contribution, we show decidability of ontology-mediated query answering in that setting and establish tight complexity bounds, namely 2ExpTime-completeness in combined complexity and coNP-completeness in data complexity. Since the lower bounds are inherited from the fragment , we concentrate on providing upper bounds. As main technical tools we establish a tree-like countermodel property and a characterization of when a query is not satisfied in a tree-like interpretation. Together, these results allow us to use an automata-based approach to query answering.

Item Type: Article
Date Type: Publication
Status: Published
Schools: Computer Science & Informatics
Publisher: Elsevier
ISSN: 0004-3702
Date of First Compliant Deposit: 17 November 2022
Date of Acceptance: 16 October 2022
Last Modified: 03 May 2023 19:36

Actions (repository staff only)

Edit Item Edit Item


Downloads per month over past year

View more statistics