Expressive cardinality constraints on ALCSCC concepts

Research output: Contribution to book/conference proceedings/anthology/reportConference contributionContributedpeer-review

Contributors

Abstract

In two previous publications we have, on the one hand, extended the description logic (DL) ALCQ by more expressive number restrictions using numerical and set constraints expressed in the quantifier-free fragment of Boolean Algebra with Presburger Arithmetic (QFBAPA). The resulting DL was called ALCSCC. On the other hand, we have extended the terminological formalism of the well-known description logic ALC from concept inclusions (CIs) to more general cardinality constraints expressed in QFBAPA, which we called extended cardinality constraints. Here, we combine the two extensions, i.e., we consider extended cardinality constraints on ALCSCC concepts. We show that this does not increase the complexity of reasoning, which is NExpTime-complete both for extended cardinality constraints in ALC and ALCSCC. The same is true for a restricted version of such cardinality constraints, where the complexity of reasoning decreases to ExpTime, not just for ALC, but also for ALCSCC.

Details

Original languageEnglish
Title of host publicationSAC '19: Proceedings of the 34th ACM/SIGAPP Symposium on Applied Computing
Pages1123-1130
Number of pages8
Publication statusPublished - 2019
Peer-reviewedYes

Publication series

SeriesSAC: Symposium on Applied Computing

Conference

Title34th Annual ACM Symposium on Applied Computing, SAC 2019
Duration8 - 12 April 2019
CityLimassol
CountryCyprus

External IDs

Scopus 85065641591
ORCID /0000-0002-4049-221X/work/142247971

Keywords

ASJC Scopus subject areas

Keywords

  • Cardinality Restrictions, Complexity, Description Logic, Number Restrictions, QFBAPA