Description Logic

Ask about this topic

Momentum

0 papers in the last four weeks, against 1 the four weeks before. 0.0% of all new papers.

Jul 13Week of Sep 28
View on map

Latest papers 12

All topics
CardsList
Aug 13, 2026cs.AI

Moose: Latent concept learning with reasoning-shortcut awareness in EL++\mathcal{EL}^{++}

The OWL 2 EL profile is used in some of the largest production ontologies, including the Gene Ontology and SNOMED CT. Existing neuro-symbolic (NeSy) learning methods accept propositional theories or Datalog, and reasoning-shortcut (RS) awareness has not been investigated in ontology settings. We present Moose, a method that compiles an EL++\mathcal{EL}^{++} TBox and finite ABox to a Sentential Decision Diagram (SDD). The SDD acts as a differentiable weighted-model-counting layer, and we add closure clauses outside the EL++\mathcal{EL}^{++} profile on declared exhaustive families to overcome the limited expressivity of EL++\mathcal{EL}^{++} under partial supervision. We show termination, soundness, completeness, and polynomial intermediate sizes, and validate the proofs in Lean. We then define the first formal partial-supervision latent-concept-learning task over an OWL EL ontology, i.e., learning per-individual classifiers for latent concepts from observed ABox literals, and evaluate Moose on MNIST-with-ontology and Pizzaïolo. Moose improves over propositional-NeSy, fuzzy-logic, and ontology embedding baselines, and presents the first reasoning-shortcut analysis in an OWL EL setting.

Olga Mashkova, Asaad Mohammedsaleh, Fernando Zhapa-Camacho +1

Computer Science Program, Computer, Electrical, and Mathematical Sciences & Engineering Division, King Abdullah University of Science and Technology, Thuwal 23955, Saudi Arabia

Neurosymbolic LearningDescription Logic
AskPDF
Aug 5, 2026cs.DB

A General Sufficient Condition for Rewriting Horn-ALCHI Atomic Queries into GQL

The emergence of the ISO standard GQL introduces a powerful query language extending first-order logic with controlled recursion, raising the question of its applicability to evaluation of ontology-mediated queries (OMQs). We focus on OMQs consisting of atomic queries over ontologies expressed in Horn-ALCHI, an expressive Description Logic that is not, in general, first-order rewritable. To address this, we introduce DL automata, a novel formalism that captures the semantics of such OMQs via runs over fact sets. We then identify a large class of DL automata that can be rewritten into unions of conjunctive two-way regular path queries (UC2RPQs), a central fragment of GQL. Our class of automata relies on a stratification of their states, ruling out specific forms of cyclic dependencies known to raise the complexity. This yields a broad class of Horn-ALCHI OMQs that are GQL-rewritable.

David Carral, Calixte Gruson, Quentin Manière

LIRMM, Inria, University of Montpellier, CNRS, Montpellier, France · DI ENS, ENS, CNRS, PSL University & Inria, France

Query ReformulationKnowledge RepresentationDescription Logic
AskPDF
Jul 23, 2026cs.AI

A New Well-Supported Semantics for Description Logic Programs

Description logic programs are a powerful formalism for combining rules with ontologies. The well-supported semantics for description logic programs ensures that no answer sets rely on cyclic dependencies. Most popular semantics for logic programming have this property of well-supportedness. We recognize two limitations of the current well-supported semantics for DL programs: its increased computational complexity for the consistency problem and its lack of a reduct transformation characterization. In this work, we present a new semantics which evaluates ontological atoms more strictly than the current semantics. This keeps the complexity of its consistency problem NP-complete, rather than increasing it to the second level of the polynomial hierarchy. Additionally, we identify a syntactic class of description logic programs for which our new semantics is equivalent to the current semantics. We characterize our semantics using a fixpoint operator and a reduct-based transformation. Our new semantics is a strict subset of the current well-supported semantics, so it maintains the prior notion of well-supportedness while inducing its own stricter notion. We prefer our new notion of well-supportedness due to its similarities with logic programming.

Spencer Killen, Jia-Huai You

University of Alberta Alberta, Canada

Logic ProgrammingAnswer Set ProgrammingDescription Logic
AskPDF
Jul 18, 2026cs.AI

Tractable Query Answering under Epistemic Confidentiality Policies in DL Ontologies (extended version)

We study Controlled Query Evaluation (CQE), a declarative approach to confidentiality-preserving data access, in the context of Description Logic (DL) ontologies, and for confidentiality policies expressed through Epistemic Dependencies (EDs). We first address the problem of answering queries (specifically, Boolean unions of conjunctive queries) under known semantics for CQE (GA- and IGA-entailment). Our results show that if the TBox is expressed in DL-LiteR\text{DL-Lite}_{\mathcal{R}}, CQE is computationally intractable in general. Moreover, in the presence of EDs, the IGA semantics has recently been proven not to satisfy an important confidentiality preservation property known as indistinguishability. With the goal of defining computationally easier and confidentiality-preserving forms of CQE, we introduce a new semantics for CQE, based on the notion of minimal policy violation (MPV). We show that the new semantics provides a sound approximation of the previous ones, while satisfying the indistinguishability property. We also prove that, in the case of DL-LiteR\text{DL-Lite}_{\mathcal{R}} ontologies, query entailment under the MPV semantics can be decided in polynomial time in data complexity. Finally, we present a software implementation of our framework that we used to evaluate the feasibility of this new approach using an existing benchmark for OWL 2 QL.

Lorenzo Marconi, Daniela Rieti, Riccardo Rosati

Sapienza University of Rome, Italy

Description Logic
AskPDF
Jun 23, 2026cs.AI

Tractable Reasoning and Conjunctive Query Answering for Defeasible DL-Lite under Rational Closure

In Description Logics (DLs), reasoning under Rational Closure (RC) is a well-known and widely accepted non-monotonic formalism to handle defeasible knowledge. In this paper, we study the application of RC to the core and horn variants of the DL-Lite family of lightweight description logics. We analyze both entitlement (instance checking) and Conjunctive Query (CQ) answering under RC. Our main contribution is providing a plug-in architecture that builds upon existing standard classical reasoners, establishing that reasoning and CQ answering under RC for DL-Lite can be done efficiently with minimal computational overhead.

Giovanni Casini, Umberto Straccia

CNR - ISTI · University of Cape Town · Istituto di Scienza e Tecnologie dell’Informazione, CNR - ISTI, Pisa, Italy +1

Logical ReasoningDescription Logic
AskPDF
May 13, 2026cs.LO

A Horn extension of DL-Lite with NL data complexity

The literature on ontology-mediated query answering (OMQA) has been shaped by two key results: first-order rewritability for DL-Lite, and PTime-hardness of data complexity for essentially every description logic beyond it. This has effectively positioned DL-Lite as the only practical choice for query rewriting, restricting OMQA solutions to first-order queries and ontologies that can be rewritten into them. This AC0 vs. PTime dichotomy is especially limiting if we consider that OMQA targets graph-structured data, and that standard graph query languages (including the recent ISO standards GQL and SQL/PGQ) are typically NL-complete. Towards identifying a rich Horn DL that can be rewritten into graph query languages and that can still express many ELI and DL-Lite ontologies, we introduce a stratification mechanism for ELI that controls the interaction between conjunction and recursion. In this way, we obtain ELbotpreceq, a description logic that strictly extends the core DL-Lite, supports reachability axioms and restricted conjunction, and allows for reasoning in NL. We establish the NL upper bound via a rewriting into nested two-way regular path queries, a fragment of GQL, providing initial evidence that our ontology language is a promising candidate for extending OMQA to graph query languages.

Janos Arpasi, Bartosz Jan Bednarczyk, Magdalena Ortiz

Institute of Logic and Computation, TU Wien · Computer Science Department, University of Wrocław

Logical ReasoningDescription Logic
AskPDF
May 2, 2026cs.AI

Rethinking Explanations: Formalizing Contrast in Description Logics

There has been a growing interest in explaining entailments over description logic (DL) knowledge bases. The existing explanation formalisms focus on justifications to explain true axioms, and abductive reasoning to explain missing axioms in a knowledge base. However, these formalisms only point out the reasoning steps behind a (missing) entailment and lack a user-centered approach as they do not consider an inquirer's needs, level of understanding, or prior knowledge. We propose contrastive explanations, aiming at answering "why an axiom P (fact) is true instead of another axiom Q (foil)" over description logic knowledge bases. The motivation arises from the observation that when a user discovers that P has occurred, they are often surprised because they anticipated the occurrence of another similar event Q. Furthermore, individual explanations for "why P" and "why not Q" are unsatisfactory since a user expects to see the difference between P and Q. In this work, we first present formal foundations of contrasting questions and then define contrastive explanations within description logics. To this end, facts include ABox assertions of the form C(x) for a concept C and individual x. Possible foils for such facts are assertions C(y) (contrasting against an individual y), or D(x) (contrasting against a concept D). Additionally, we explore the properties of contrastive explanations in the DL EL and ALC. We also provide an implementation of our definition and an experimental evaluation on KBs of varying sizes.

Yasir Mahmood, Arnab Sharma, Axel-Cyrille Ngonga Ngomo +1

Data Science Group, Heinz Nixdorf Institute, Paderborn University Germany

Logical ReasoningExplainable Artificial IntelligenceCounterfactual ExplanationsDescription Logic
AskPDF
May 2, 2026cs.LO

ABox Abduction for Inconsistent Knowledge Bases under Repair Semantics

Given a knowledge base (KB) with a non-entailed fact, the ABox abduction problem asks for possible extensions of the KB that would entail this fact. This problem has many applications, ranging from diagnosis to explainability and repair. ABox abduction has been well-investigated for consistent KBs and classical semantics, but little is known for the case of inconsistent KBs, which can be caused by erroneous data. In this paper we define suitable notions of abduction in this setting and propose criteria that guide abduction towards "useful" hypotheses. To regain meaningful reasoning in the presence of inconsistencies, we use well-established repair semantics. We provide a comprehensive landscape of the complexity of ABox abduction under repair semantics, treating different variants of the abduction problem for the light-weight description logics DL-Lite and EL_bot.

Anselm Haak, Patrick Koopmann, Yasir Mahmood +1

Knowledge Representation Group, Paderborn University, Germany · Knowledge in Artificial Intelligence, Vrije Universiteit Amsterdam, The Netherlands · Data Science Group, Paderborn University, Germany

Logical ReasoningAbductive ReasoningDescription Logic
AskPDF
Apr 28, 2026cs.LO

Fitting Horn DL Ontologies to ABox and Query Examples: A Tale of Simulation Quantifiers and Finite Models

We study the problem of fitting a description logic (DL) ontology to a given set of positive and negative examples that take the form of an ABox and a Boolean query. While previous work has investigated this problem for the expressive DLs ALC and ALCI, we here focus on the Horn DLs EL and ELI, as well as their extensions with the bottom concept. As the query language, we consider atomic queries (AQs), conjunctive queries (CQs), and unions thereof (UCQs). We provide characterization of the existence of a fitting ontology based on simulations, use them to develop decision procedures, and clarify the exact computational complexity. For AQs, the problem is in PTime for both EL and ELI. For CQs and UCQs, it is Σ2PΣ_2^P-complete for EL and ExpTime-complete for ELI. Adding the bottom concept does not change any of these complexities. Interestingly, moving from ALC and ALCI to EL and ELI introduces additional technical challenges rather than simplifying the matter.

Marvin Grosser, Carsten Lutz

Leipzig University · ScaDS.AI Center Dresden/Leipzig

Logical ReasoningDescription LogicOntology Learning
AskPDF
Apr 27, 2026cs.AI

BoxLitE: A Faithful Knowledge Base Embedding Based on Convex Optimization

Knowledge base (KB) embeddings aim at combining the capability of classical knowledge graph embeddings to generalize the information present in facts, the ABox, with conceptual knowledge represented in an ontology language, the TBox. Several authors have recently explored the idea of mapping concepts to convex regions in a vector space. This is useful to represent hierarchies, typically present in TBoxes, since more general concepts can be mapped to larger regions, containing those regions associated with more specific concepts. However, the power of convexity is rarely leveraged during the actual learning tasks. Here, we introduce BoxLitE, a KB embedding model for DL-LiteH^{\mathcal{H}} that allows for convex optimization. We show that for any satisfiable DL-LiteH^{\mathcal{H}} KB, there is a BoxLitE embedding that is a weakly faithful model. As a proof of concept, we show how to formulate the KB embedding task as a convex optimization problem and how to obtain embeddings with such desirable faithfulness properties.

Bruno F. Lourenço, Hesham Morgan, Ana Ozaki +2

The Institute of Statistical Mathematics, Japan · TU Wien, Austria · University of Oslo, Norway +1

Logical ReasoningKG EmbeddingKnowledge RepresentationKnowledge GraphsDescription Logic
AskPDF
Apr 23, 2026cs.LO

TAPO-Description Logic for Information Behavior: Refined OBoxes, Inference, and Categorical Semantics

This paper develops a refined version of TAPO-description logic for the analysis of information behavior. The framework is treated not as a single homogeneous object logic, but as a layered formalism consisting of a static descriptive layer (TBox/ABox), a procedural layer (PBox), and an oracle-sensitive layer (OBox). To make this architecture mathematically explicit, we introduce a metalevel guard-judgment layer governing procedural branching and iteration. On this basis we formulate a core inference system for TAPO-description logic, covering static TBox/ABox reasoning, guarded procedural transition in the PBox, and validated external import in the OBox. We then give a categorical semantics for the resulting framework and indicate its sheaf-theoretic refinement. The theory is illustrated by examples of information-seeking behavior, including simple search behavior and review-sensitive ordering behavior in a curry restaurant. The aim is to treat not only static knowledge representation but also hesitation, external consultation, and action-guiding update within a unified logical setting.

Takao Inoué

Logical ReasoningDescription Logic
AskPDF
Mar 12, 2020cs.LO

Querying and Repairing Inconsistent Prioritized Knowledge Bases: Complexity Analysis and Links with Abstract Argumentation

In this paper, we explore the issue of inconsistency handling over prioritized knowledge bases (KBs), which consist of an ontology, a set of facts, and a priority relation between conflicting facts. In the database setting, a closely related scenario has been studied and led to the definition of three different notions of optimal repairs (global, Pareto, and completion) of a prioritized inconsistent database. After transferring the notions of globally-, Pareto- and completion-optimal repairs to our setting, we study the data complexity of the core reasoning tasks: query entailment under inconsistency-tolerant semantics based upon optimal repairs, existence of a unique optimal repair, and enumeration of all optimal repairs. Our results provide a nearly complete picture of the data complexity of these tasks for ontologies formulated in common DL-Lite dialects. The second contribution of our work is to clarify the relationship between optimal repairs and different notions of extensions for (set-based) argumentation frameworks. Among our results, we show that Pareto-optimal repairs correspond precisely to stable extensions (and often also to preferred extensions), and we propose a novel semantics for prioritized KBs which is inspired by grounded extensions and enjoys favourable computational properties. Our study also yields some results of independent interest concerning preference-based argumentation frameworks.

Meghyn Bienvenu, Camille Bourgaux

CNRS & University of Bordeaux, France · DI ENS, ENS, CNRS, PSL University & Inria, Paris, France

Logical ReasoningComputational ArgumentationDescription Logic
AskPDF