%0 Journal Article %1 Baader2019-ap %A Baader, Franz %D 2019 %I Association for Computing Machinery (ACM) %J ACM SIGAPP Appl. Comput. Rev. %K %N 3 %P 5--17 %T Expressive cardinality restrictions on concepts in a description logic with expressive number restrictions %V 19 %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 the DL ALC and in its extension 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.

@article{Baader2019-ap, 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 the DL ALC and in its extension 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}, author = {Baader, Franz}, biburl = {https://puma.scadsai.uni-leipzig.de/bibtex/22145b605991d56edc696d00a3a91dac7/scadsfct}, copyright = {http://www.acm.org/publications/policies/copyright\_policy\#Background}, interhash = {b80b585bfbd01fc4926e78ca359d60f2}, intrahash = {2145b605991d56edc696d00a3a91dac7}, journal = {ACM SIGAPP Appl. Comput. Rev.}, keywords = {}, language = {en}, month = nov, number = 3, pages = {5--17}, publisher = {Association for Computing Machinery (ACM)}, timestamp = {2024-09-10T15:15:57.000+0200}, title = {Expressive cardinality restrictions on concepts in a description logic with expressive number restrictions}, volume = 19, year = 2019 }