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

• URL: http://arxiv.org/abs/2604.26976v1
• Date: Tue, 28 Apr 2026 08:53:15 GMT
• Title: Fitting Horn DL Ontologies to ABox and Query Examples: A Tale of Simulation Quantifiers and Finite Models
• Abstract summary: We study the problem of fitting a description logic (DL) ontology to a set of positive and negative examples.<n>We consider atomic queries (AQs), conjunctive queries (rooted CQs), and unions thereof (rooted UCQs)<n>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.
• Score: 5.134998749955833
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: 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 (rooted CQs), and unions thereof (rooted 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 rooted CQs and UCQ, it is Sigma_P^2-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.

Related papers

• How Hard is it to Decide if a Fact is Relevant to a Query? [1.6058099298620423]
  Given a database D, a Boolean conjunctive query (CQ) q, and fact f in D, decide whether f is relevant to q wrt.<n>We identify self-joins (multiple atoms with the same relation) as the culprit.<n>Our results thus pinpoint what makes relevance harder than query evaluation and identify natural classes of queries which admit efficient relevance computation.
  arXiv  Detail & Related papers  (2026-04-24T10:29:27Z)
• OrLog: Resolving Complex Queries with LLMs and Probabilistic Reasoning [51.58235452818926]
  We introduce OrLog, a neuro-symbolic retrieval framework that decouples predicate-level plausibility estimation from logical reasoning.<n>A large language model (LLM) provides plausibility scores for atomic predicates in one decoding-free forward pass, from which a probabilistic reasoning engine derives the posterior probability of query satisfaction.
  arXiv  Detail & Related papers  (2026-01-30T15:31:58Z)
• The benefits of query-based KGQA systems for complex and temporal questions in LLM era [55.20230501807337]
  Large language models excel in question-answering (QA) yet still struggle with multi-hop reasoning and temporal questions.<n> Query-based knowledge graph QA (KGQA) offers a modular alternative by generating executable queries instead of direct answers.<n>We explore multi-stage query-based framework for WikiData QA, proposing multi-stage approach that enhances performance on challenging multi-hop and temporal benchmarks.
  arXiv  Detail & Related papers  (2025-07-16T06:41:03Z)
• Querying Circumscribed Description Logic Knowledge Bases [9.526604375441073]
  Circumscription is one of the main approaches for defining non-monotonic description logics. We prove decidability of (U)CQ evaluation on circumscribed DL KBs. We also study the much simpler atomic queries (AQs)
  arXiv  Detail & Related papers  (2023-06-07T15:50:15Z)
• Complex Query Answering on Eventuality Knowledge Graph with Implicit Logical Constraints [48.831178420807646]
  We propose a new framework to leverage neural methods to answer complex logical queries based on an EVentuality-centric KG. Complex Eventuality Query Answering (CEQA) considers the implicit logical constraints governing the temporal order and occurrence of eventualities. We also propose a Memory-Enhanced Query (MEQE) to significantly improve the performance of state-of-the-art neural query encoders on the CEQA task.
  arXiv  Detail & Related papers  (2023-05-30T14:29:24Z)
• An Empirical Comparison of LM-based Question and Answer Generation Methods [79.31199020420827]
  Question and answer generation (QAG) consists of generating a set of question-answer pairs given a context. In this paper, we establish baselines with three different QAG methodologies that leverage sequence-to-sequence language model (LM) fine-tuning. Experiments show that an end-to-end QAG model, which is computationally light at both training and inference times, is generally robust and outperforms other more convoluted approaches.
  arXiv  Detail & Related papers  (2023-05-26T14:59:53Z)
• Reasoning over Hierarchical Question Decomposition Tree for Explainable Question Answering [83.74210749046551]
  We propose to leverage question decomposing for heterogeneous knowledge integration. We propose a novel two-stage XQA framework, Reasoning over Hierarchical Question Decomposition Tree (RoHT) Experiments on complex QA datasets KQA Pro and Musique show that our framework outperforms SOTA methods significantly.
  arXiv  Detail & Related papers  (2023-05-24T11:45:59Z)
• The Price of Selfishness: Conjunctive Query Entailment for ALCSelf is 2ExpTime-hard [11.193504036335503]
  In logic-based knowledge representation, query answering has essentially replaced mere satisfiability checking. For knowledge bases in the basic description logic ALC, the computational complexity of conjunctive query (CQ) answering is well known to be ExpTime-complete. We show that even extending ALC by just the Self operator increases the complexity of CQ entailment to 2ExpTime.
  arXiv  Detail & Related papers  (2021-06-29T08:12:03Z)
• Actively Learning Concepts and Conjunctive Queries under ELr-Ontologies [22.218000867486726]
  We show that EL-concepts are not query learnable in the presence of ELI-ontologies. We also show that EL-concepts are not query learnable in the presence of ELI-ontologies.
  arXiv  Detail & Related papers  (2021-05-18T07:45:37Z)
• CQE in Description Logics Through Instance Indistinguishability (extended version) [0.0]
  We study privacy-preserving query answering in Description Logics (DLs) We derive data complexity results query answering over DL-Lite$_mathcal$$. We identify a semantically well-founded notion of approximated confidentiality answering for CQE.
  arXiv  Detail & Related papers  (2020-04-24T17:28:24Z)
• Conditional Self-Attention for Query-based Summarization [49.616774159367516]
  We propose textitconditional self-attention (CSA), a neural network module designed for conditional dependency modeling. Experiments on Debatepedia and HotpotQA benchmark datasets show CSA consistently outperforms vanilla Transformer.
  arXiv  Detail & Related papers  (2020-02-18T02:22:31Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.