Journal
ARTIFICIAL INTELLIGENCE
Volume 313, Issue -, Pages -Publisher
ELSEVIER
DOI: 10.1016/j.artint.2022.103785
Keywords
Logical separability; Decidable fragments of first -order logic; Description logic; Learning from examples; Complexity; Ontologies
Categories
Funding
- DFG [CRC 1320 EASE]
- EPSRC [EP/S032207/1]
Ask authors/readers for more resources
This paper investigates the existence of a logical formula for separating positive and negative examples in the presence of an ontology. The study focuses on different logic languages and separation methods, and compares their separating power and computational complexity.
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. (c) 2022 Elsevier B.V. All rights reserved.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available