Learning algebraic structures from text

The present work investigates the learnability of classes of substructures of some algebraic structures: submonoids and subgroups of given groups, ide als of given commutative rings, subfields of given vector spaces. The learn er sees all positive data but no negative one and converges to a program en umerating or computing the set to be learned. Besides semantical (BC) and s yntactical (Ex) convergence also the more restrictive ordinal bounds on the number of mind changes are considered. The following is shown: (a) Learnab ility depends much on the amount of semantic knowledge given at the synthes is of the learner where this knowledge is represented by programs for the a lgebraic operations, codes for prominent elements of the algebraic structur e (like 0 and 1 fields) and certain parameters (like the dimension of finit e-dimensional vector spaces). For several natural examples, good knowledge of the semantics may enable to keep ordinal mind change bounds while restri cted knowledge may either allow only BC-convergence or even not permit lear nability at all. (b) The class of all ideals of a recursive ring is BC-lear nable iff the ring is Noetherian. Furthermore, one has either only a BC-lea mer outputting enumerable indices or one can already get an Ex-learner conv erging to decision procedures and respecting an ordinal bound on the number of mind changes. The ring is Artinian iff the ideals can be Ex-learned wit h a constant bound on the number of mind changes, this constant is the leng th of the ring. Ex-learnability depends not only on the ring but also on th e representation of the ring. Polynomial rings over the field of rationals with n variables have exactly the ordinal mind change bound omega (n) in th e standard representation. Similar results can be established for unars. No etherian unars with one function can be learned with an ordinal mind change bound aw for some a. (C) 2001 Elsevier Science B.V. All rights reserved.