Minimal Model Reasoning in Description Logics: Don’t Try This at Home!
Federica Di Stefano, Quentin Manière, Magdalena Ortiz, Mantas Šimkus \affiliations Institute of Logic, Compuation, TU Wien · 2025
Read Minimal Model Reasoning in Description Logics: Don’t Try This at Home! by Federica Di Stefano, Quentin Manière, Magdalena Ortiz, Mantas Šimkus \affiliations Institute of Logic, Compuation, TU Wien (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2508-05350.txt.
Introduction
Federica Di Stefano and co-authors study minimal model reasoning in description logics in this 2025 paper. Minimal models sit at the core of many knowledge representation methods. Circumscription style minimization for chosen predicates was known to be complex. Pure minimal models, where every predicate extension must be minimal, stayed uncharted.
The results are strikingly negative. Concept satisfiability in minimal models is undecidable even for a light logic, EL. The blow extends to a narrow fragment of tuple generating dependencies. Acyclicity conditions on the rule set restore decidability below double exponential time. Links to pointwise circumscription follow. The DL-Lite family adds a hardness result of its own. The title warns readers not to try this at home.
Catalog record
| CREATOR | Federica Di Stefano, Quentin Manière, Magdalena Ortiz, Mantas Šimkus \affiliations Institute of Logic, Compuation, TU Wien |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 65 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2508-05350
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Minimal Model Reasoning in Description Logics: Don’t Try This at Home! Federica Di Stefano, Quentin Manière, Magdalena Ortiz, Mantas Šimkus \affiliations Institute of Logic, Compuation, TU Wien 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 core \textup{DL-Lite}_{\textup{core}} , but our investigation establishes 𝖤𝗑𝗉𝖲𝗉𝖺𝖼𝖾 \mathsf{ExpSpace} -hardness already for its extension DL-Lite horn \textup{DL-Lite}_{\textup{horn}} . 1 Introduction Reasoning with minimal models has always been at the core of many Knowledge Representation (KR) languages. It is most prominent in formalisms for non-monotonic reasoning, from default logic [ \citeauthoryearReiter1980 ] and circumscription [ \citeauthoryearMcCarthy1980 ] to answer set programming [ \citeauthoryearGelfond and Lifschitz1988 ] and it plays a crucial role in classical KR problems like abduction and diagnosis [ \citeauthoryearReiter1987 ] . Finding minimal models and reasoning about them has been a recurring topic in the KR literature for many years; see [ \citeauthoryearBen-Eliyahu and Dechter1996 , \citeauthoryearBen-Eliyahu-Zohary and Palopoli1997 , \citeauthoryearLackner and Pfandler2012 , \citeauthoryearAngiulli et al.2014 , \citeauthoryearPfandler, Pichler, and Woltran2014 ] . When reasoning from a knowledge base, minimal models provide a natural and intuitive counterpart to traditional open-world semantics and classical entailment, which can easily exclude some expected consequences (e.g., a query may be not entailed due to a counter-example model that includes unexpected and unjustified facts). In contrast, considering only those models in which all facts are strictly necessary and justified may lead to more intuitive reasoning. We illustrate this in a very simple example. Example 1 . Under the standard semantics, the inclusion \mathsf{ScandCountry}\sqsubseteq\mathsf{NatoMember} is not entailed by the following six assertions, since there may be unknown Scandinavian countries that are not in NATO: \mathsf{ScandCountry}(no) , \mathsf{ScandCountry}(se) , \mathsf{ScandCountry}(dk) , \mathsf{NatoMember}(no) , \mathsf{NatoMember}(se) , \mathsf{NatoMember}(dk) . However, the entailment does hold under the minimal model semantics; equivalently, the concept \mathsf{ScandCountry}\sqcap\lnot\mathsf{NatoMember} is not satisfiable in the minimal models. Despite the strong motivation, there are still big gaps in our understanding of minimal model reasoning in Description Logics (DLs) . Predicate minimization has been explored in the context of circumscription in DLs , but most existing results spell out the high complexity that results from combining minimized predicates with varying or fixed predicates; see, e.g., [ \citeauthoryearBonatti, Lutz, and Wolter2009 , \citeauthoryearLutz, Manière, and Nolte2023 ] . Specifically, when varying predicates are allowed (e.g. satisfiability of a concept for general circumscription in \mathcal{ALC} ), reasoning becomes quickly undecidable. But the case of purely minimal models , where nothing can be removed from the extension of any predicate while preserving modelhood, remained largely unexplored. It was however established recently that for the DL \mathcal{ELIO} —a relatively expressive DL with ExpTime -complete concept satisfiability problem for classical semantics—basic minimal model reasoning becomes undecidable [ \citeauthoryearDi Stefano and Šimkus2024 ] . A positive result was established for \textup{DL-Lite}_{\textup{core}} : here minimal model reasoning exhibits the same worst-case complexity as in the classical case [ \citeauthoryearBonatti et al.2023 ] . It is thus natural to explore whether similar positive or negative results can be obtained for other lightweight DLs like \mathcal{EL} or other DL-Lite variants. In this paper we investigate these questions, and provide the following contributions: • We show that concept satisfiability in a minimal model is undecidable for the DL \mathcal{EL} . The decidability status of minimal model reasoning has been open for several years, and the negative outcome is somewhat surprising. It contrasts with the complexity of the classical semantics for \mathcal{EL} , which supports tractable reasoning for basic reasoning tasks. Our undecidability proof does not use the \top -concept, and it thus carries over to guarded tuple generating dependencies (TGDs) of very restricted shapes. • To regain decidability, we impose two types of acyclicity conditions on the TBox, which are defined in terms of a dependency graph on the predicates of a knowledge base. If we restrict our attention to strongly acyclic TBoxes, we can import results from pointwise circumscription of [ \citeauthoryearDi Stefano, Ortiz, and Simkus2023 ] to show that \mathcal{ELIO} not only becomes decidable, but is feasible in non-deterministic exponential time. We also explore weak acyclicity , a common notion in the setting of TGDs in database theory [ \citeauthoryearFagin et al.2005 , \citeauthoryearAlviano, Morak, and Pieris2017 , \citeauthoryearGrau et al.2013 ] . Weakly acyclic \mathcal{EL} and \mathcal{ELIO} remain decidable; we get tight \mathsf{NExp}^{\mathsf{NP}} bounds on combined complexity, and \Sigma_{2}^{P} on data complexity. • We conclude the paper with a minor excursion into DL-Lite, but even there we find a challenging panorama: satisfiability in minimal models is already \mathsf{ExpSpace} -hard for \textup{DL-Lite}_{\textup{horn}} . The present document, with full proofs in the appendix, is the long version of a paper published at KR 2025. 2 Preliminaries We briefly recall the syntax and semantics of DLs studied in this paper and refer to [ \citeauthoryearBaader et al.2017 ] for more details. We consider countably infinite pairwise disjoint sets \mathsf{N_{C}} , \mathsf{N_{R}} and \mathsf{N_{I}} of concept , role and individual names , respectively, and use \mathsf{N_{R}^{\pm}} to denote the set \mathsf{N_{R}}\cup\{r^{-}\mid r\in\mathsf{N_{R}}\} . Concepts in \mathcal{ALCIO} follow the syntax C:=A\mid\{a\}\mid\top\mid\lnot C\mid C\sqcap C\mid\exists r.C , where A\in\mathsf{N_{C}} , r\in\mathsf{N_{R}^{\pm}} and a\in\mathsf{N_{I}} . By removing negated concepts \lnot C from this grammar, we obtain concepts in \mathcal{ELIO} ; by removing nominals \{a\} and requiring r\in\mathsf{N_{R}} we obtain \mathcal{ALC} . The intersection of the \mathcal{ELIO} and \mathcal{ALC} concept languages is called \mathcal{EL} . In \mathcal{ELIO}_{\bot} and \mathcal{EL_{\bot}} we extend \mathcal{ELIO} and \mathcal{EL} with negation, but only in concepts of the form \lnot\top , which we equivalently write \bot . In \mathcal{ALCIO} we use C\sqcup D as a shortcut for \lnot(\lnot C\sqcap\lnot D) and \forall r.C as a shortcut for \lnot(\exists r.\lnot C) . Let \mathcal{L} be a DL. A TBox \mathcal{T} (in \mathcal{L} ) is a finite set of concept inclusions C\sqsubseteq D where C and D are concepts in \mathcal{L} . An ABox \mathcal{A} is a finite set of assertions of the forms A(a) and r(a,b) with A\in\mathsf{N_{C}} , r\in\mathsf{N_{R}^{\pm}} and a,b\in\mathsf{N_{I}} . A pair \mathcal{K}=(\mathcal{T},\mathcal{A}) of a TBox and an ABox is a knowledge base (KB) . The semantics of DLs is defined using interpretations \mathcal{I}=(\Delta^{\mathcal{I}},\cdot^{\mathcal{I}}) , where \Delta^{\mathcal{I}} is a non-empty domain and the interpretation function \cdot^{\mathcal{I}} maps each A\in\mathsf{N_{C}} to a set A^{\mathcal{I}}\subseteq\Delta^{\mathcal{I}} , each r\in\mathsf{N_{R}} to a set of pairs r^{\mathcal{I}}\subseteq\Delta^{\mathcal{I}}\times\Delta^{\mathcal{I}} , and each a\in\mathsf{N_{I}}