Exact Learning Description Logic Ontologies from Data Retrieval Examples

(2015) Exact Learning Description Logic Ontologies from Data Retrieval Examples. In: 28th International Workshop on Description Logics, June 7th to 10th, 2015, Athens.

Text paper-30.pdf - Published Version Download (323kB)

Abstract

We investigate the complexity of learning description logic TBoxes in Angluin et al.’s framework of exact learning via queries posed to an oracle. We consider membership queries of the form “is individual a a certain answer to a data retrieval query q of ABox A and the target TBox?” and equivalence queries of the form “is a given TBox equivalent to the target TBox?”. We show that (i) DL-Lite TBoxes with role inclusions and ELI-concept expressions on the right-hand side of inclusions and (ii) EL TBoxes without complex concept expressions on the right-hand side of inclusions can be learned in polynomial time. Both results are proved by a non-trivial reduction to learning from subsumption examples. We also show that arbitrary EL TBoxes cannot be learned in polynomial time.

Item Type:	Conference or Workshop Item (Paper)
Subjects:	Q Science > QA Mathematics > QA75 Electronic computers. Computer science
Depositing User:	Symplectic Admin
Date Deposited:	31 Mar 2016 10:09
Last Modified:	31 Mar 2016 10:09
:	Copyright © 2015 for the individual papers by the papers' authors. Copying permitted for private and academic purposes. This volume is published and copyrighted by its editors.
URI:	http://livrepository.liverpool.ac.uk/id/eprint/2022489

Repository Staff Access