# On the Power and Limitations of Examples for Description Logic Concepts

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 6 of its 33 references that are in the map.
- First posted on arXiv 23 Dec 2024.

## Builds on (most cited first, 6 of 6)

- [The DL-Lite Family and Relations](https://mlsanity.com/paper/1401.3487/) (2014)
- [Learning Description Logic Ontologies. Five Approaches. Where Do They Stand?](https://mlsanity.com/paper/2104.01193/) (2021)
- [Conjunctive Queries: Unique Characterizations and Exact Learnability](https://mlsanity.com/paper/2008.06824/) (2020)
- [Frontiers and Exact Learning of ELI Queries under DL-Lite Ontologies](https://mlsanity.com/paper/2204.14172/) (2022)
- [Unique Characterisability and Learnability of Temporal Instance Queries](https://mlsanity.com/paper/2205.01651/) (2022)
- [Characterising Modal Formulas with Examples](https://mlsanity.com/paper/2206.06049/) (2022)

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

- [Model Change for Description Logic Concepts](https://mlsanity.com/paper/2603.05562/) (2026)
- [Shapes from Examples: Foundations of Shape Learning in Recursive SHACL](https://mlsanity.com/paper/2607.27934/) (2026)

## Abstract (arXiv)

Labeled examples (i.e., positive and negative examples) are an attractive medium for communicating complex concepts. They are useful for deriving concept expressions (such as in concept learning, interactive concept specification, and concept refinement) as well as for illustrating concept expressions to a user or domain expert. We investigate the power of labeled examples for describing description-logic concepts. Specifically, we systematically study the existence and efficient computability of finite characterisations, i.e. finite sets of labeled examples that uniquely characterize a single concept, for a wide variety of description logics between EL and ALCQI, both without an ontology and in the presence of a DL-Lite ontology. Finite characterisations are relevant for debugging purposes, and their existence is a necessary condition for exact learnability with membership queries.