Logical Separability of Incomplete Data under Ontologies

1^st June 2020, 15:00
Hadrien Pulcini
University of Liverpool

Abstract

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, and generating referring expressions. In this paper, we investigate the existence of a separating formula for incomplete data in the presence of an ontology. Both for the ontology language and the separation language, we concentrate on first-order logic and three important fragments thereof: the description logic ALCI, the guarded fragment, and the two-variable fragment. We consider several forms of separability that differ in whether or not they admit the use of additional helper symbols to achieve separation and in the treatment of negative examples. We aim to characterise separability in a model-theoretic way, to compare the separating power of the different languages, and to determine the computational complexity of separability as a decision problem.