Fitting Horn DL Ontologies to ABox and Query Examples: A Tale of Simulation Quantifiers and Finite Models
Not on the map. Why?
Abstract (arXiv)
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 Sigma2P-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.
Key facts. No citing papers in the map yet (data through 7 Oct 2026). Builds on 8 of its 37 references that are in the map. First posted on arXiv 28 Apr 2026.
Builds on
8 of 37 references.
References · 8
- 2020Logical Separability of Labeled Data Examples under Ontologiescited by 10
- 2016The complexity of reverse engineering problems for conjunctive queriescited by 7
- 2023SAT-Based PAC Learning of Description Logic Conceptscited by 5
- 2018Finite Query Answering in Expressive Description Logics with Transitive Rolescited by 4
- 2013Model Theoretic Characterisations of Description Logicscited by 2
- 2025Fitting Description Logic Ontologies to ABox and Query Examplescited by 2
- 2020From Conjunctive Queries to Instance Queries in Ontology-Mediated Queryingcited by 1
- 2025Fitting Ontologies and Constraints to Relational Structurescited by 1
Built on by
Not cited yet.