# Logical Separability of Labeled Data Examples under Ontologies

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

## Key facts

- Cited by 10 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 3 Jul 2020.

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

- [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)
- [Current and Future Challenges in Knowledge Representation and Reasoning](https://mlsanity.com/paper/2308.04161/) (2023)
- [Fitting Ontologies and Constraints to Relational Structures](https://mlsanity.com/paper/2508.13176/) (2025)
- [Unique Characterisability and Learnability of Temporal Queries Mediated by an Ontology](https://mlsanity.com/paper/2306.07662/) (2023)
- [Data Complexity in Expressive Description Logics With Path Expressions](https://mlsanity.com/paper/2406.07095/) (2024)
- [Interpolation in Knowledge Representation](https://mlsanity.com/paper/2512.08833/) (2025)
- [Navigating Taxonomic Expansions of Entity Sets Driven by Knowledge Bases](https://mlsanity.com/paper/2512.16953/) (2025)
- [Fitting Horn DL Ontologies to ABox and Query Examples: A Tale of Simulation Quantifiers and Finite Models](https://mlsanity.com/paper/2604.26976/) (2026)
- [Bounded Fitting for Expressive Description Logics](https://mlsanity.com/paper/2605.07452/) (2026)

## Abstract (arXiv)

Finding a logical formula that separates positive and negative examples given in the form of labeled data items is fundamental in applications such as concept learning, reverse engineering of database queries, generating referring expressions, and entity comparison in knowledge graphs. In this paper, we investigate the existence of a separating formula for data in the presence of an ontology. Both for the ontology language and the separation language, we concentrate on first-order logic and the following important fragments thereof: the description logic ALCI, the guarded fragment, the two-variable fragment, and the guarded negation fragment. For separation, we also consider (unions of) conjunctive queries. We consider several forms of separability that differ in the treatment of negative examples and in whether or not they admit the use of additional helper symbols to achieve separation. Our main results are model-theoretic characterizations of (all variants of) separability, the comparison of the separating power of different languages, and the investigation of the computational complexity of deciding separability.