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 $\mathcal{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.

翻译：找到一个逻辑公式,将以标签数据项目形式给出的正面和负面实例区分开来,对于概念学习、数据库查询的反向工程、参考表达方式和知识图中的实体比较等应用至关重要。在本文中,我们调查在本体学面前存在数据分离公式的情况。对于本体学语言和分离语言,我们集中研究第一阶逻辑及其中以下重要部分:描述逻辑$\mathcal{ALCI}$、保守碎片、两可变碎片和保守的否定碎片。为了分离,我们还考虑(结合)结合查询。我们考虑了在处理负面例子和是否接受使用额外辅助符号实现分离方面有所不同的几种分离形式。我们的主要结果是模型――理论――(所有变式)分离特征、不同语言分离能力的比较以及决定分离的计算复杂性调查。