%0 Conference Paper %1 Baader2019-yq %A Baader, Franz %B Proceedings of the 34th ACM/SIGAPP Symposium on Applied Computing %C New York, NY, USA %D 2019 %I ACM %K %T Expressive cardinality constraints on ALCSCC concepts %X 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.

@inproceedings{Baader2019-yq, 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.}, added-at = {2024-09-10T11:56:37.000+0200}, address = {New York, NY, USA}, author = {Baader, Franz}, biburl = {https://puma.scadsai.uni-leipzig.de/bibtex/2bd99d71549a77b534a8d746a2191ee68/scadsfct}, booktitle = {Proceedings of the 34th {ACM/SIGAPP} Symposium on Applied Computing}, conference = {SAC '19: The 34th ACM/SIGAPP Symposium on Applied Computing}, copyright = {http://www.acm.org/publications/policies/copyright\_policy\#Background}, interhash = {7727e8481efec57f06338e90e8967b26}, intrahash = {bd99d71549a77b534a8d746a2191ee68}, keywords = {}, location = {Limassol Cyprus}, month = apr, publisher = {ACM}, timestamp = {2024-09-10T15:15:57.000+0200}, title = {Expressive cardinality constraints on {\textit{ALCSCC}} concepts}, year = 2019 }