Minimal Model Reasoning in Description Logics: Don't Try This at Home!
Authors:
Preprint
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 $\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}}$.
Keywords
All Related Versions
This publication has 14 references indexed in Scilit:
- The complexity of handling minimal solutions in logic-based abductionJournal of Logic and Computation, 2014
- Rectangular tileability and complementary tileability are undecidableEuropean Journal of Combinatorics, 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