Exact Learning of Lightweight Description Logic Ontologies

From International Center for Computational Logic

Toggle side column

Exact Learning of Lightweight Description Logic Ontologies

Boris KonevBoris Konev,  Carsten LutzCarsten Lutz,  Ana OzakiAna Ozaki,  Frank WolterFrank Wolter
Exact Learning of Lightweight Description Logic Ontologies


Boris Konev, Carsten Lutz, Ana Ozaki, Frank Wolter
Exact Learning of Lightweight Description Logic Ontologies
Principles of Knowledge Representation and Reasoning, July 2014. AAAI Press
  • KurzfassungAbstract
    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 ELI concepts on the right-hand side of concept inclusions can be learned in polynomial time; (2) EL TBoxes with only concept names on the right-hand side of concept inclusions can be learned in polynomial time; and (3) EL TBoxes cannot be learned in polynomial time. It follows that non-polynomial time learnability of EL 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.
  • Forschungsgruppe:Research Group: Wissensbasierte Systeme
@inproceedings{KLOW2014,
  author    = {Boris Konev and Carsten Lutz and Ana Ozaki and Frank Wolter},
  title     = {Exact Learning of Lightweight Description Logic Ontologies},
  booktitle = {Principles of Knowledge Representation and Reasoning},
  publisher = {AAAI Press},
  year      = {2014},
  month     = {July}
}