Actively Learning Concepts and Conjunctive Queries under ELr-Ontologies
  We consider the problem to learn a concept or a query in the presence of an
ontology formulated in the description logic ELr, in Angluin's framework of
active learning that allows the learning algorithm to interactively query an
oracle (such as a domain expert). We show that the following can be learned in
polynomial time: (1) EL-concepts, (2) symmetry-free ELI-concepts, and (3)
conjunctive queries (CQs) that are chordal, symmetry-free, and of bounded
arity. In all cases, the learner can pose to the oracle membership queries
based on ABoxes and equivalence queries that ask whether a given concept/query
from the considered class is equivalent to the target. The restriction to
bounded arity in (3) can be removed when we admit unrestricted CQs in
equivalence queries. We also show that EL-concepts are not polynomial query
learnable in the presence of ELI-ontologies.
