Minimal Model Reasoning in Description Logics: Don't Try This at Home!
This addresses foundational limitations in knowledge representation for AI, revealing severe computational barriers in minimal model reasoning, which is incremental as it builds on prior circumscription work.
The paper tackles the problem of reasoning with pure minimal models in Description Logics, finding that concept satisfiability is undecidable for basic DLs like EL, and establishes ExpSpace-hardness for extensions like DL-Litehorn, with some decidability regained under acyclicity conditions at worst-case complexity below double exponential time.
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 $\mathcal{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$_{\text{core}}$, but our investigation establishes ExpSpace-hardness already for its extension DL-Lite$_{\text{horn}}$.