Minimal Model Reasoning in Description Logics: Don’t Try This at Home!
Authors:
Open Access
- 1 November 2025
- conference paper
- Published by International Joint Conferences on Artificial Intelligence
- Vol. 22 (1) , 271-280
Abstract
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.Keywords
All Related Versions
This publication has 14 references indexed in Scilit:
- Rectangular tileability and complementary tileability are undecidableEuropean Journal of Combinatorics, 2014
- On the tractability of minimal model computation for some CNF theoriesArtificial Intelligence, 2014
- Towards more expressive ontology languages: The query answering problemArtificial Intelligence, 2012
- Data exchange: semantics and query answeringTheoretical Computer Science, 2005
- Reasoning with minimal models: efficient algorithms and applicationsArtificial Intelligence, 1997
- On computing minimal modelsAnnals of Mathematics and Artificial Intelligence, 1996
- On the computational cost of disjunctive logic programming: Propositional caseAnnals of Mathematics and Artificial Intelligence, 1995
- Complete Problems Involving Boolean Labelled Structures and Projection TransactionsJournal of Logic and Computation, 1991
- A theory of diagnosis from first principlesArtificial Intelligence, 1987
- A logic for default reasoningArtificial Intelligence, 1980