Ordinal mind change complexity of language identification

The approach of ordinal mind change complexity, introduced by Freivalds and Smith, uses (notations for) constructive ordinals to bound the number of m ind changes made by a learning machine. This approach provides a measure of the extent to which a learning machine has to keep revising its estimate o f the number of mind changes it will make before converging to a correct hy pothesis for languages in the class being learned. Recently, this notion, w hich also yields a measure for the difficulty of learning a class of langua ges, has been used to analyze the learnability of rich concept classes. The present paper further investigates the utility of ordinal mind change c omplexity. It is shown that for identification from both positive and negat ive data and n greater than or equal to 1, the ordinal mind change complexi ty of the class of languages formed by unions of up to n + 1 pattern langua ges is only omega x(O) notn(n) (where notn(n) is a notation for n, omega is a notation for the least limit ordinal and x(O) represents ordinal multipl ication). This result nicely extends an observation of Lange and Zeugmann t hat pattern languages can be identified from both positive and negative dat a with 0 mind changes. Existence of an ordinal mind change bound for a class of learnable language s can be seen as an indication of its learning "tractability". Conditions a re investigated under which a class has an ordinal mind change bound for id entification from positive data. It is shown that an indexed family of lang uages has an ordinal mind change bound if it has finite elasticity and can be identified by a conservative machine. It is also shown that the requirem ent of conservative identification can be sacrificed for the purely topolog ical requirement of M-finite thickness. Interaction between identification by monotonic strategies and existence of ordinal mind change bound is also investigated, (C) 1999 Elsevier Science B.V. All rights reserved.