Exact Learning of Lightweight Description Logic Ontologies


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

Warning
There is a more recent version of this item available.
[thumbnail of learningDLRevision.pdf] Text
learningDLRevision.pdf - Author Accepted Manuscript
Download (663kB)

Abstract

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 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: 23 May 2026 05:28
DOI: 10.5555/3031929.3031966
Related Websites:
URI: https://livrepository.liverpool.ac.uk/id/eprint/3017175
Disclaimer: The University of Liverpool is not responsible for content contained on other websites from links within repository metadata. Please contact us if you notice anything that appears incorrect or inappropriate.

Available Versions of this Item

Altmetric
CORE (COnnecting REpositories)