{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,13]],"date-time":"2026-02-13T08:56:19Z","timestamp":1770972979106,"version":"3.50.1"},"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":[[2025,11]]},"abstract":"<jats:p>Reasoning with minimal models has always been at the core of many knowledge representation techniques, but we still have only a limited understanding of this problem in Description Logics (DLs). Minimization of some selected predicates---letting the remaining predicates vary or be fixed, as proposed in circumscription---has been explored and exhibits high complexity. The case of `pure' minimal models, where the extension of all predicates must be minimal, has remained largely uncharted. We address this problem in popular DLs and obtain surprisingly negative results: concept satisfiability in minimal models is undecidable already for EL. This undecidability also extends to a very restricted fragment of tuple-generating dependencies. To regain decidability, we impose acyclicity conditions on the TBox that bring the worst-case complexity below double exponential time and allow us to establish a connection with the recently studied pointwise circumscription; we also derive results in data complexity. We conclude with a brief excursion to the DL-Lite family, where a positive result was known for DL-Lite_core, but our investigation establishes ExpSpace-hardness already for its extension DL-Lite_horn.<\/jats:p>","DOI":"10.24963\/kr.2025\/27","type":"proceedings-article","created":{"date-parts":[[2025,11,5]],"date-time":"2025-11-05T06:10:44Z","timestamp":1762323044000},"page":"271-280","source":"Crossref","is-referenced-by-count":1,"title":["Minimal Model Reasoning in Description Logics: Don\u2019t Try This at Home!"],"prefix":"10.24963","author":[{"given":"Federica","family":"Di Stefano","sequence":"first","affiliation":[{"name":"Institute of Logic and Compuation, TU Wien"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Quentin","family":"Mani\u00e8re","sequence":"additional","affiliation":[{"name":"Universit\u00e4t Leipzig"},{"name":"ScaDS.AI"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Magdalena","family":"Ortiz","sequence":"additional","affiliation":[{"name":"Institute of Logic and Compuation, TU Wien"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Mantas","family":"\u0160imkus","sequence":"additional","affiliation":[{"name":"Institute of Logic and Compuation, TU Wien"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"10584","event":{"name":"22nd International Conference on Principles of Knowledge Representation and Reasoning {KR-2025}","theme":"Artificial Intelligence","location":"Melbourne, Australia","acronym":"KR-2025","number":"22","sponsor":["Artificial Intelligence Journal","Principles of Knowledge Representation and Reasoning Inc.","Academic College of Tel-Aviv","European Association for Artificial Intelligence","National Science Foundation"],"start":{"date-parts":[[2025,11,11]]},"end":{"date-parts":[[2025,11,17]]}},"container-title":["Proceedings of the TwentySecond International Conference on Principles of Knowledge Representation and Reasoning"],"original-title":[],"deposited":{"date-parts":[[2025,11,5]],"date-time":"2025-11-05T06:11:04Z","timestamp":1762323064000},"score":1,"resource":{"primary":{"URL":"https:\/\/proceedings.kr.org\/2025\/27"}},"subtitle":[],"proceedings-subject":"Artificial Intelligence Research Articles","short-title":[],"issued":{"date-parts":[[2025,11]]},"references-count":0,"URL":"https:\/\/doi.org\/10.24963\/kr.2025\/27","relation":{},"subject":[],"published":{"date-parts":[[2025,11]]}}}