Logical separability of incomplete data under ontologies

Jung, JC, Lutz, C, Pulcini, H and Wolter, F ORCID: 0000-0002-4470-606X (2020) Logical separability of incomplete data under ontologies In: International Conference on Principles of Knowledge Representation and Reasoning, 2020-9-10 - 2020-9-16, Rhodes.

Text KR2020separation.pdf - Author Accepted Manuscript Download (365kB) | Preview

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 the treatment of negative examples and in whether or not they admit the use of additional helper symbols to achieve separation. We characterize separability in a model-theoretic way, compare the separating power of the different languages, and determine the computational complexity of separability as a decision problem.

Item Type:	Conference Item (Unspecified)
Additional Information:	Full Version of KR'20 paper
Uncontrolled Keywords:	cs.LO, cs.LO, cs.AI
Depositing User:	Symplectic Admin
Date Deposited:	06 Jul 2020 10:59
Last Modified:	21 Apr 2026 20:43
Related Websites:	Author
URI:	https://livrepository.liverpool.ac.uk/id/eprint/3092806
Disclaimer:	The University of Liverpool is not responsible for content contained on other websites from links within repository metadata. Please contact us if you notice anything that appears incorrect or inappropriate.