On finite and unrestricted query entailment beyond SQ with number restrictions on transitive roles

Gogacz, Tomasz, Gutierrez-Basulto, Victor ORCID: https://orcid.org/0000-0002-6117-5459, Ibanez-Garcia, Yazmin ORCID: https://orcid.org/0000-0002-1276-904X, Jung, Jean Christoph and Murlak, Filip 2019. On finite and unrestricted query entailment beyond SQ with number restrictions on transitive roles. Presented at: 28th International Joint Conference on Artificial Intelligence (IJCAI-19), Macao, China, 10-16 August 2019. Proceedings of the Twenty-Eighth International Joint Conference on Artificial Intelligence. International Joint Conferences on Artificial Intelligence, pp. 1719-1725. 10.24963/ijcai.2019/238

Preview

PDF - Accepted Post-Print Version Download (348kB) | Preview

Abstract

We study the description logic SQ with number restrictions applicable to transitive roles, extended with either nominals or inverse roles. We show tight 2EXPTIME upper bounds for unrestricted entailment of regular path queries for both extensions and finite entailment of positive existential queries for nominals. For inverses, we establish 2EXPTIME-completeness for unrestricted and finite entailment of instance queries (the latter under restriction to a single, transitive role).

Item Type:	Conference or Workshop Item (Paper)
Date Type:	Publication
Status:	Published
Schools:	Schools > Computer Science & Informatics
Publisher:	International Joint Conferences on Artificial Intelligence
Funders:	ERC Starting grant 637277 FLEXILOG
Date of First Compliant Deposit:	28 June 2019
Date of Acceptance:	10 May 2019
Last Modified:	11 Aug 2025 14:45
URI:	https://orca.cardiff.ac.uk/id/eprint/123826

Citation Data

Cited 1 time in Scopus. View in Scopus. Powered By Scopus® Data

Actions (repository staff only)

Edit Item