  Concept Induction refers to the problem of creating complex Description Logic
class descriptions (i.e., TBox axioms) from instance examples (i.e., ABox
data). In this paper we look particularly at the case where both a set of
positive and a set of negative instances are given, and complex class
expressions are sought under which the positive but not the negative examples
fall. Concept induction has found applications in ontology engineering, but
existing algorithms have fundamental performance issues in some scenarios,
mainly because a high number of invokations of an external Description Logic
reasoner is usually required. In this paper we present a new algorithm for this
problem which drastically reduces the number of reasoner invokations needed.
While this comes at the expense of a more limited traversal of the search
space, we show that our approach improves execution times by up to several
orders of magnitude, while output correctness, measured in the amount of
correct coverage of the input instances, remains reasonably high in many cases.
Our approach thus should provide a strong alternative to existing systems, in
particular in settings where other systems are prohibitively slow.
