Expressive cardinality constraints on ALCSCC concepts

Publikation: Beitrag in Buch/Konferenzbericht/Sammelband/GutachtenBeitrag in KonferenzbandBeigetragenBegutachtung

Beitragende

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

OriginalspracheEnglisch
TitelSAC '19: Proceedings of the 34th ACM/SIGAPP Symposium on Applied Computing
Seiten1123-1130
Seitenumfang8
PublikationsstatusVeröffentlicht - 2019
Peer-Review-StatusJa

Publikationsreihe

ReiheSAC: Symposium on Applied Computing

Konferenz

Titel34th Annual ACM Symposium on Applied Computing, SAC 2019
Dauer8 - 12 April 2019
StadtLimassol
LandZypern

Externe IDs

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

Schlagworte

ASJC Scopus Sachgebiete

Schlagwörter

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