THE LEARNABILITY OF DESCRIPTION LOGICS WITH EQUALITY CONSTRAINTS

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.