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.

There is a more recent version of this item available.

Text
learningDLRevision.pdf - Author Accepted Manuscript
Download (663kB)

Official URL: http://www.aaai.org/Library/KR/kr14contents.php

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 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:	Author Publisher
URI:	https://livrepository.liverpool.ac.uk/id/eprint/3017175