Expressive cardinality constraints on ALCSCC concepts
Research output: Contribution to book/conference proceedings/anthology/report › Conference contribution › Contributed › peer-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 language | English |
---|---|
Title of host publication | SAC '19: Proceedings of the 34th ACM/SIGAPP Symposium on Applied Computing |
Pages | 1123-1130 |
Number of pages | 8 |
Publication status | Published - 2019 |
Peer-reviewed | Yes |
Publication series
Series | SAC: Symposium on Applied Computing |
---|
Conference
Title | 34th Annual ACM Symposium on Applied Computing, SAC 2019 |
---|---|
Duration | 8 - 12 April 2019 |
City | Limassol |
Country | Cyprus |
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