TY - JOUR AU - Jung, Jean Christoph AU - Lutz, Carsten AU - Wolter, Frank PY - 2020/04/03 Y2 - 2024/03/28 TI - Least General Generalizations in Description Logic: Verification and Existence JF - Proceedings of the AAAI Conference on Artificial Intelligence JA - AAAI VL - 34 IS - 03 SE - AAAI Technical Track: Knowledge Representation and Reasoning DO - 10.1609/aaai.v34i03.5675 UR - https://ojs.aaai.org/index.php/AAAI/article/view/5675 SP - 2854-2861 AB - <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 <span style="font-variant: small-caps;">co</span>NP-complete for LCS and MSC verification in the description logic <em>εℒ</em> without TBoxes to undecidability of LCS and MSC verification and existence in <em>εℒI</em> 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 <em>εℒI</em> with TBoxes and study single example MSC as a special case.</p> ER -