# Minimal Model Reasoning in Description Logics: Don't Try This at Home!

arXiv: https://arxiv.org/abs/2508.05350 · HTML: https://mlsanity.com/paper/2508.05350/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 3 of its 23 references that are in the map.
- First posted on arXiv 7 Aug 2025.

## Builds on (most cited first, 3 of 3)

- [Acyclicity Notions for Existential Rules and Their Application to Query Answering in Ontologies](https://mlsanity.com/paper/1406.4110/) (2014)
- [On the Tractability of Minimal Model Computation for Some CNF Theories](https://mlsanity.com/paper/1310.8120/) (2013)
- [Querying Circumscribed Description Logic Knowledge Bases](https://mlsanity.com/paper/2306.04546/) (2023)

## Abstract (arXiv)

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-Litecore, but our investigation establishes ExpSpace-hardness already for its extension DL-Litehorn.