Least General Generalizations in Description Logic: Verification and Existence



Jung, Jean Christoph, Lutz, Carsten and Wolter, Frank
(2020) Least General Generalizations in Description Logic: Verification and Existence. .

[img] Text
ijcai20_ELU.pdf - Author Accepted Manuscript

Download (533kB) | Preview

Abstract

We study two forms of least general generalizations in description logic, the least common subsumer (LCS) and most specific concept (MSC). While the LCS generalizes from examples that take the form of concepts, the MSC generalizes from individuals in data. Our focus is on the complexity of existence and verification, the latter meaning to decide whether a candidate concept is the LCS or MSC. We consider cases with and without a background TBox and a target signature. Our results range from CONP-complete for LCS and MSC verification in the description logic EL without TBoxes to undecidability of LCS and MSC verification and existence in ELI with TBoxes. To obtain results in the presence of a TBox, we establish a close link between the problems studied in this paper and concept learning from positive and negative examples. We also give a way to regain decidability in ELI with TBoxes and study single example MSC as a special case.

Item Type: Conference or Workshop Item (Unspecified)
Depositing User: Symplectic Admin
Date Deposited: 07 Jul 2020 08:30
Last Modified: 18 Jan 2023 23:47
Related URLs:
URI: https://livrepository.liverpool.ac.uk/id/eprint/3092804