# Exact Learning of Lightweight Description Logic Ontologies

arXiv: https://arxiv.org/abs/1709.07314 · HTML: https://mlsanity.com/paper/1709.07314/

## Key facts

- Cited by 10 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 20 Sep 2017.

## Built on by (most cited first, 10 of 10)

- [Towards Ontology Construction with Language Models](https://mlsanity.com/paper/2309.09898/) (2023)
- [Learning Description Logic Ontologies. Five Approaches. Where Do They Stand?](https://mlsanity.com/paper/2104.01193/) (2021)
- [Neural Class Expression Synthesis](https://mlsanity.com/paper/2111.08486/) (2021)
- [Actively Learning Concepts and Conjunctive Queries under ELr-Ontologies](https://mlsanity.com/paper/2105.08326/) (2021)
- [Frontiers and Exact Learning of ELI Queries under DL-Lite Ontologies](https://mlsanity.com/paper/2204.14172/) (2022)
- [Fitting Description Logic Ontologies to ABox and Query Examples](https://mlsanity.com/paper/2508.08007/) (2025)
- [On the Complexity of Learning Description Logic Ontologies](https://mlsanity.com/paper/2103.13694/) (2021)
- [From Subsumption to Satisfiability: LLM-Assisted Active Learning for OWL Ontologies](https://mlsanity.com/paper/2604.16672/) (2026)
- [Unique Characterisability and Learnability of Temporal Queries Mediated by an Ontology](https://mlsanity.com/paper/2306.07662/) (2023)
- [Extracting PAC Decision Trees from Black Box Binary Classifiers: The Gender Bias Case Study on BERT-based Language Models](https://mlsanity.com/paper/2412.10513/) (2024)

## Abstract (arXiv)

We study the problem of learning description logic (DL) ontologies in Angluin et al.'s framework of exact learning via queries. We admit membership queries ("is a given subsumption entailed by the target ontology?") and equivalence queries ("is a given ontology equivalent to the target ontology?"). We present three main results: (1) ontologies formulated in (two relevant versions of) the description logic DL-Lite can be learned with polynomially many queries of polynomial size; (2) this is not the case for ontologies formulated in the description logic EL, even when only acyclic ontologies are admitted; and (3) ontologies formulated in a fragment of EL related to the web ontology language OWL 2 RL can be learned in polynomial time. We also show that neither membership nor equivalence queries alone are sufficient in cases (1) and (3).