Separating Data Examples by Description Logic Concepts with Restricted\n Signatures

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