# Separating Data Examples by Description Logic Concepts with Restricted Signatures

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

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 12 Jul 2021.

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

- [SAT-Based PAC Learning of Description Logic Concepts](https://mlsanity.com/paper/2305.08511/) (2023)
- [Fitting Description Logic Ontologies to ABox and Query Examples](https://mlsanity.com/paper/2508.08007/) (2025)
- [Reverse Engineering of Temporal Queries Mediated by LTL Ontologies](https://mlsanity.com/paper/2305.01248/) (2023)
- [Fitting Ontologies and Constraints to Relational Structures](https://mlsanity.com/paper/2508.13176/) (2025)
- [Interpolation in Knowledge Representation](https://mlsanity.com/paper/2512.08833/) (2025)

## Abstract (arXiv)

We study the separation of positive and negative data examples in terms of description logic concepts in the presence of an ontology. In contrast to previous work, we add a signature that specifies a subset of the symbols that can be used for separation, and we admit individual names in that signature. We consider weak and strong versions of the resulting problem that differ in how the negative examples are treated and we distinguish between separation with and without helper symbols. Within this framework, we compare the separating power of different languages and investigate the complexity of deciding separability. While weak separability is shown to be closely related to conservative extensions, strongly separating concepts coincide with Craig interpolants, for suitably defined encodings of the data and ontology. This enables us to transfer known results from those fields to separability. Conversely, we obtain original results on separability that can be transferred backward. For example, rather surprisingly, conservative extensions and weak separability in ALCO are both 3ExpTime-complete.