Exact Learning of Lightweight Description Logic Ontologies

Konev, Boris ORCID: 0000-0002-6507-0494, Lutz, Carsten, Ozaki, Ana and Wolter, Frank
(2014) Exact Learning of Lightweight Description Logic Ontologies. In: Principles of Knowledge Representation and Reasoning, 2014-7-20 - 2014-7-24, Vienna Technical University.

WarningThere is a more recent version of this item available.
[img] Text
learningDLRevision.pdf - Author Accepted Manuscript

Download (663kB)


We study learning of description logic TBoxes in Angluin et al.'s framework of exact learning via queries. We admit entailment queries ("is a given subsumption entailed by the target TBox'") and equivalence queries ("is a given TBox equivalent to the target TBox'"), assuming that the signature and logic of the target TBox are known. We present three main results: (1) TBoxes formulated in DL-Lite with role inclusions and composite concepts on the right-hand side of concept inclusions can be learned in polynomial time; (2) εL TBoxes with only concept names on the right-hand side of concept inclusions can be learned in polynomial time; and (3) εL TBoxes cannot be learned in polynomial time. It follows that non-polynomial time learnability of εL TBoxes is caused by the interaction between existential restrictions on the right-and left-hand sides of concept inclusions. We also show that neither entailment nor equivalence queries alone are sufficient in cases (1) and (2) above.

Item Type: Conference or Workshop Item (Unspecified)
Additional Information: ## TULIP Type: Conference Proceedings (contribution) ##
Uncontrolled Keywords: Exact Learning, Description Logic, Complexity
Depositing User: Symplectic Admin
Date Deposited: 31 Jan 2018 07:48
Last Modified: 19 Jan 2023 06:42
DOI: 10.5555/3031929.3031966
Related URLs:
URI: https://livrepository.liverpool.ac.uk/id/eprint/3017175

Available Versions of this Item