{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T17:16:07Z","timestamp":1760202967127},"publisher-location":"California","reference-count":0,"publisher":"International Joint Conferences on Artificial Intelligence Organization","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2020,7]]},"abstract":"<jats:p>Concrete domains, especially those that allow to compare features with numeric values, have long been recognized as a very desirable extension of description logics (DLs), and significant efforts have been invested into adding them to usual DLs while  keeping the complexity of reasoning in check. For expressive DLs and in the presence of general TBoxes, for standard reasoning tasks like consistency, the most general decidability results are for the so-called \u03c9-admissible domains, which are required to be dense. Supporting non-dense domains for features that range over integers or natural numbers remained largely open, despite often being singled out as a highly desirable extension. The decidability of some extensions of ALC with non-dense domains has been shown, but existing results rely on powerful machinery that does not allow to infer any elementary bounds on the complexity of the problem. In this paper, we study an extension of ALC with a rich integer domain that allows for comparisons (between features, and between features and constants coded in unary), and prove that consistency can be solved using automata-theoretic techniques in single exponential time, and thus has no higher worst-case complexity than standard ALC. Our upper bounds apply to some extensions of DLs with concrete domains known from the literature, support general TBoxes, and allow for comparing values along paths of ordinary (not necessarily functional) roles.<\/jats:p>","DOI":"10.24963\/kr.2020\/61","type":"proceedings-article","created":{"date-parts":[[2020,8,20]],"date-time":"2020-08-20T00:39:16Z","timestamp":1597883956000},"page":"614-623","source":"Crossref","is-referenced-by-count":5,"title":["An ExpTime Upper Bound for ALC with Integers"],"prefix":"10.24963","author":[{"given":"Nadia","family":"Labai","sequence":"first","affiliation":[{"name":"Vienna University of Technology"}]},{"given":"Magdalena","family":"Ortiz","sequence":"additional","affiliation":[{"name":"Vienna University of Technology"}]},{"given":"Mantas","family":"\u0160imkus","sequence":"additional","affiliation":[{"name":"Vienna University of Technology"}]}],"member":"10584","event":{"number":"17","sponsor":["Artificial Intelligence Journal","Principles of Knowledge Representation and Reasoning Inc.","Association for Logic Programming","Center for Perspicuous Computing","European Association for Artificial Intelligence","Ontopic - The Virtual Knowledge Graph Company"],"acronym":"KR-2020","name":"17th International Conference on Principles of Knowledge Representation and Reasoning {KR-2020}","start":{"date-parts":[[2020,9,12]]},"theme":"Artificial Intelligence","location":"Rhodes, Greece","end":{"date-parts":[[2020,9,18]]}},"container-title":["Proceedings of the Seventeenth International Conference on Principles of Knowledge Representation and Reasoning"],"original-title":[],"deposited":{"date-parts":[[2020,11,5]],"date-time":"2020-11-05T16:18:44Z","timestamp":1604593124000},"score":1,"resource":{"primary":{"URL":"https:\/\/proceedings.kr.org\/2020\/61"}},"subtitle":[],"proceedings-subject":"Artificial Intelligence Research Articles","short-title":[],"issued":{"date-parts":[[2020,7]]},"references-count":0,"URL":"https:\/\/doi.org\/10.24963\/kr.2020\/61","relation":{},"subject":[],"published":{"date-parts":[[2020,7]]}}}