Home Page




Editorial Board


Open Source Software




Frequently Asked Questions

Contact Us

RSS Feed

Exact Learning of Lightweight Description Logic Ontologies

Boris Konev, Carsten Lutz, Ana Ozaki, Frank Wolter; 18(201):1−63, 2018.


We study the problem of learning description logic (DL) ontologies in Angluin et al.'s framework of exact learning via queries. We admit membership queries (“is a given subsumption entailed by the target ontology?”) and equivalence queries (“is a given ontology equivalent to the target ontology?”). We present three main results: (1) ontologies formulated in (two relevant versions of) the description logic DL-Lite can be learned with polynomially many queries of polynomial size; (2) this is not the case for ontologies formulated in the description logic $\mathcal{E}\mathcal{L}$, even when only acyclic ontologies are admitted; and (3) ontologies formulated in a fragment of $\mathcal{E}\mathcal{L}$ related to the web ontology language OWL 2 RL can be learned in polynomial time. We also show that neither membership nor equivalence queries alone are sufficient in cases (1) and (3).

© JMLR 2018. (edit, beta)