Least General Generalizations in Description Logic: Verification and Existence

Jung, Jean Christoph, Lutz, Carsten and Wolter, Frank ORCID: 0000-0002-4470-606X (2020) Least General Generalizations in Description Logic: Verification and Existence. .

Text
ijcai20_ELU.pdf - Author Accepted Manuscript
Download (533kB) | Preview

Official URL: http://dx.doi.org/10.1609/aaai.v34i03.5675

Abstract

<jats:p>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 εℒ without TBoxes to undecidability of LCS and MSC verification and existence in εℒI 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 εℒI with TBoxes and study single example MSC as a special case.</jats:p>

Item Type:	Conference or Workshop Item (Unspecified)
Depositing User:	Symplectic Admin
Date Deposited:	07 Jul 2020 08:30
Last Modified:	25 Mar 2024 09:45
DOI:	10.1609/aaai.v34i03.5675
Related URLs:	Author Publisher
URI:	https://livrepository.liverpool.ac.uk/id/eprint/3092804