Although there is an increasing amount of experimental research on lea
rning concepts expressed in first-order logic, there are still relativ
ely few formal results on the polynomial learnability of first-order r
epresentations from examples. Most previous analyses in the pac-model
have focused on subsets of Prolog, and only a few highly restricted su
bsets have been shown to be learnable. In this paper, we will study in
stead the learnability of the restricted first-order logics known as '
'description logics'', also sometimes called ''terminological logics''
or ''KL-ONE-type languages''. Description logics are also subsets of
predicate calculus, but are expressed using a different syntax, allowi
ng a different set of syntactic restrictions to be explored. We first
define a simple description logic, summarize some results on its expre
ssive power, and then analyze its learnability. It is shown that the f
ull logic cannot be tractably learned. However, syntactic restrictions
exist that enable tractable learning from positive examples alone, in
dependent of the size of the vocabulary used to describe examples. The
learnable sublanguage appears to be incomparable in expressive power
to any subset of first-order logic previously known to be learnable.